N=800;
H=[-9865659,-8898614,-8738750,-8680326,-8448319,-7681858,-7624678,-6504594,-6104127,-6112078,-5195347,-5226837,-4301295,-3723879,-3666107,-2749213,-2767590,-2122959,-1252425,-1058973,-22302178,-21886689,-20969976,-20854333,-20357301,-19873324,-18997375,-18072138,-17719870,-17389348,-16751738,-16651856,-16390685,-15442947,-14334813,-13534058,-13025076,-12126003,-11317082,-10879685,-30899797,-30172164,-29637581,-29477236,-29130957,-28563797,-28121497,-27438121,-26333544,-26425171,-25605757,-25539421,-25204929,-25072131,-24833879,-24863847,-24107272,-23009902,-22987337,-22982195,-39638490,-38799743,-38275030,-37814590,-36772470,-36097126,-35396986,-34556527,-34556519,-34310976,-33979310,-34058746,-33405412,-32836572,-32213227,-32210593,-32015929,-31649552,-31490959,-31205387,-51783122,-51297854,-51364828,-50962287,-50255998,-50020473,-49285429,-48807737,-47816947,-46760813,-45906040,-45348747,-44825590,-44789273,-43727629,-42647797,-42678991,-42066717,-40945901,-40609865,-58846523,-58348156,-58432563,-58466998,-58345743,-57352883,-57374939,-57142933,-56684054,-56543728,-55898445,-55225807,-55236993,-55083374,-54437469,-53558159,-53282146,-53338855,-52589838,-52347011,-67812771,-67148544,-66803902,-66133585,-65334371,-65339736,-65127035,-65014637,-64783157,-63977641,-63318553,-63282236,-62373652,-61660118,-61309009,-60359057,-60323983,-60246184,-60297768,-59177899,-78551220,-77921920,-77895486,-76959981,-76459345,-75693083,-74806243,-73764104,-73715344,-73776258,-73049279,-72863328,-72108971,-71078632,-70275164,-70121704,-70059644,-69739071,-68792613,-68642228,-84749658,-84872594,-84613236,-84529941,-84220048,-84214334,-83668593,-83765632,-83733854,-83355678,-82922590,-82704629,-82008376,-81048240,-80958659,-79939012,-79466167,-79502229,-79248425,-78815071,-94854657,-93891247,-93736500,-93019288,-92354153,-91610964,-90980368,-89902860,-89417905,-89322330,-88906046,-88593295,-87955133,-87786588,-86697552,-86560458,-86672717,-86069923,-85806633,-85311227,-105224033,-104617383,-103951705,-102926300,-102306733,-102040906,-102123067,-101404321,-100525160,-99420639,-99095107,-98918619,-98511471,-97547627,-96606237,-96231744,-95962129,-95403111,-94907515,-94836777,-111222206,-110973964,-110862096,-110937817,-110755808,-110878431,-109834971,-109437555,-109225954,-109292072,-108799778,-108301179,-108090381,-108031545,-108060304,-108180165,-107896797,-106857622,-106055298,-106167447,-121754514,-121659921,-121404326,-120309495,-119726821,-119680417,-119102873,-118445190,-117758047,-117039936,-117043459,-116088801,-115507331,-115112411,-114817819,-114707752,-113879914,-112870435,-112442683,-111512830,-130860123,-129823344,-129431538,-128865369,-128765528,-128173382,-128122006,-127367511,-127314327,-126948185,-126740994,-126422884,-125355972,-124509167,-124256790,-123687995,-123696901,-123063639,-122206826,-122089996,-138639682,-137632508,-137563457,-137007318,-136520414,-136188159,-136243917,-135773818,-135350711,-134737644,-134842274,-134900754,-134346392,-133893466,-133185648,-133047096,-132418388,-132039234,-131564553,-130971445,-149975399,-149407426,-148860250,-148315040,-147263089,-146772368,-145778191,-145459293,-144815018,-144584575,-143962550,-143482474,-143133834,-142242528,-141771930,-140993115,-140802077,-140655127,-139679192,-139494102,-161150347,-160315227,-159650146,-158729271,-157872766,-157040066,-156840942,-156438028,-156339911,-155265011,-155307112,-154372144,-153316392,-153075242,-152940182,-152411266,-151784761,-151879496,-150910770,-150670613,-172184104,-171850207,-171061101,-170797194,-170528079,-170294922,-169570171,-168537763,-167709476,-166641114,-166165847,-165252845,-164892823,-164280650,-163662403,-163310949,-162963420,-161980084,-162047811,-161390439,-183658502,-182677823,-182331909,-182096799,-181769891,-181482145,-180859723,-180890482,-180607868,-180309082,-179617362,-179117693,-178664892,-177977182,-176897768,-175790696,-175306213,-174709270,-173698527,-172996556,-191568408,-190665306,-190325925,-189853850,-189700908,-188700406,-187659478,-187463148,-187080958,-186851709,-186078831,-185531617,-185579462,-185356944,-185111307,-184998891,-184918222,-184936211,-185018359,-184095345,0,995237,1448560,1918709,2635494,2732210,3685077,4119614,4179366,4573649,5316269,6268023,6639956,7745553,8528976,8626737,9678074,10112595,10417656,11067312,11585283,12334539,13406610,14058233,14662768,15148132,15240690,15136985,15074276,15804858,16917773,17486334,18372105,19264880,19536190,20364140,20624329,21077848,21090050,21582746,22624390,23155950,23242781,24111140,24548981,25082400,25434085,25716633,26250141,26477086,26841397,27710605,28804011,29170461,29862041,30798613,30791406,31117702,32089813,32809135,33545660,34560759,35435726,35925512,36200476,36492466,36857585,37911270,37813516,37733916,38806058,39193390,39578843,40272605,40315451,41218779,42015932,42631987,43619212,43938687,43867227,44037473,44278343,45200444,46116450,46947963,48053706,48475929,48752241,48863705,49164022,50159584,50622956,51539690,52070675,52158771,53051838,54128639,54439787,54854051,55359568,56174605,56211628,56781577,57675972,58730189,58717224,59061999,59308062,59222925,60251830,61123861,62051094,63152110,63201840,63759263,64284650,64496903,65505845,66448020,66744345,67093183,67896103,68528030,68732486,68635315,68819579,69938413,71059515,70966005,71465947,71407556,71780260,71774859,71653032,72495931,73510833,74014318,75017651,75176158,75795383,76871804,77555618,77973979,78786542,79084965,79089712,79540134,80139074,80405839,80850522,81213877,81997747,82196019,83101667,83076517,83752710,84722879,85468147,86041765,86245476,87317780,87825682,88789240,89206968,89371575,89686911,90193349,90322738,90410672,90300523,90202199,90080647,90775119,91500399,91819470,92601568,92773572,93613348,94220494,94667145,95644484,95737528,96245069,97049441,97343065,97677694,98792519,99855646,100968320,101553884,102649643,102591847,102543050,103618252,104188221,105027402,106111133,106949757,107015540,106917446,107687682,107832305,107945146,108323647,109021622,109987982,110836849,111488879,111382764,112019423,111985370,112316113,112273447,112862962,113866510,114494726,114399922,114486666,114833527,114771361,115275545,115313803,115484164,116229355,117234269,117478865,117567609,118374592,118963604,119145561,120125789,120405809,121156616,121295319,122197291,122389505,123478773,123427745,123940388,124217451,124644062,124596753,124747274,124671017,125544135,126145845,126561972,126705356,127161610,128195681,128114832,128421418,129324021,129739098,130831402,131839401,132292408,132917530,133863367,134093429,134176648,134170623,134582557,134669376,134916303,135561660,135881560,136305917,137241770,137162471,137740807,138628788,138571674,139696634,139777838,140568339,141084150,141263109,141592549,142271386,143272966,143899833,144144518,144748765,145202952,146259037,146789937,147862676,148751021,149733914,150722232,150764427,151128921,151399343,151601940,152100803,153151159,154233551,154612288,155102272,155387380,156251823,156415146,156768554,156739600,156944234,156863494,157801422,157951507,158000671,158867548,159108908,159941268,160488768,160606792,160490697,160388113,161061858,161434231,162037436,162311803,163323585,164045054,164900802,165361976,165555130,166424835,166995099,167336097,167914624,167964163,168701900,169037940,169098427,169792621,169807581,170070001,171132450,171422179,171834906,172908670,173215429,174136605,174500340,174673556,175365942,175680070,176054894,176342224,176898043,177263854,177660337,178561828,178745071,178651143,179065049,179820837,180323056,181267722,181712663,182713980,182844688,183887745,184739647,185738983,186329718,186655421,186660858,187585720,188564349,189485040,189870116,190896211,190897777,191139329,191699036,192759058,192706583,193577373,193497065,193799698,194195236,194625506,195156465,195803205,196664835,197048788,197818225,198246719,198671232,198590393,198601849,198944586,199298128,199298957,199684206,200071668,200129448,201029504];
X0=597830444;
M=10000;
S=[716,126,447,598,333,45,671,780,349,411,79,578,701,649,47,535,140,54,797,460,330,738,699,287,247,557,392,786,276,535,132,164,224,129,16,21,795,522,74,646,421,434,84,22,127,153,558,549,488,576,342,83,672,38,654,1,583,427,533,750,638,368,555,474,228,243,49,421,89,534,645,495,157,472,297,633,369,506,157,290,244,155,735,523,102,731,81,178,519,122,626,665,568,632,706,191,344,534,578,292,199,723,112,41,581,239,142,333,627,458,60,368,496,389,728,722,60,639,580,20,535,664,671,341,162,529,745,21,732,8,579,276,677,671,331,114,702,21,355,528,229,11,171,333,412,32,705,298,226,52,231,549,536,583,508,512,508,729,384,378,48,459,500,211,51,348,566,652,454,652,488,100,7,699,618,443,600,298,346,721,728,600,538,775,520,389,297,540,166,306,39,368,148,29,117,515,401,232,721,501,222,210,349,455,473,796,281,472,388,325,419,105,478,493,253,632,168,436,102,647,384,474,478,53,264,160,6,642,223,517,60,367,454,265,450,571,411,620,248,358,480,655,572,304,116,593,16,442,88,402,723,227,458,755,69,107,76,658,7,210,157,497,279,313,286,592,343,446,301,365,327,387,748,138,741,712,442,486,371,75,24,129,720,526,740,443,380,368,704,565,216,49,331,270,226,50,166,518,220,754,687,349,102,625,40,180,254,79,272,362,294,621,168,415,285,554,686,84,163,646,676,39,441,449,745,602,445,540,382,589,593,437,641,638,341,750,468,431,391,263,214,543,713,670,488,206,378,341,232,476,186,203,600,458,42,384,695,407,680,661,358,643,598,169,35,14,564,28,368,409,800,654,76,483,508,256,632,172,615,177,466,437,417,577,412,348,235,432,181,675,163,767,30,394,555,44,789,655,675,537,732,340,777,710,690,408,703,49,376,379,548,92,204,317,56,38,176,95,348,623,771,512,398,216,454,800,208,480,119,63,322,615,728,606,610,77,328,476,658,51,232,505,529,792,790,182,447,796,788,177,509,767,65,652,649,98,446,487,69,579,393,192,49,516,100,505,651,261,430,497,341,452,360,616,302,643,592,670,502,545,552,404,686,575,143,329,148,603,454,221,362,311,555,369,208,370,320,323,772,396,388,373,264,230,568,262,667,95,26,279,765,343,748,326,623,110,557,597,336,645,94,36,160,506,765,433,351,239,492,478,141,4,106,490,619,567,248,309,280,202,52,575,436,668,416,521,224,654,411,434,635,126,326,218,293,366,351,386,798,573,328,296,390,715,736,398,606,345,40,627,741,230,606,344,315,466,676,251,289,285,761,446,694,232,158,449,762,529,81,642,365,346,404,131,175,643,486,323,97,42,648,98,354,689,760,224,338,663,344,702,306,765,423,443,481,641,422,759,479,517,531,403,684,40,48,429,552,234,572,391,84,108,664,384,431,13,546,505,537,365,604,368,531,76,133,711,732,651,702,702,692,136,421,115,59,485,732,680,529,130,130,636,471,29,376,623,492,184,124,577,112,530,80,563,228,716,499,420,359,356,742,404,345,764,103,196,26,691,344,434,554,41,216,192,426,703,648,653,409,532,134,570,87,104,84,357,37,123,17,720,226,366,670,603,558,383,121,452,617,336,4,653,595,417,606,341,109,112,392,60,150,191,288,418,14,781,392,488,342,475,575,493,525,647,326,177,51,755,667,309,648,478,256,599,780,296,148,633,96,722,280,666,739,411,330,603,437,259,460,795,311,650,669,729,136,177,318,568,712,470,525,469,663,508,236,146,85,192,666,46,771,675,504,361,352,422,100,195,108,200,672,61,104,298,363,662,499,586,742,238,173,650,687,774,630,777,328,380,462,327,112,242,502,197,456,7,205,322,398,28,211,318,644,656,169,377,265,738,174,788,478,469,418,493,641,294,357,39,116,215,215,191,246,423,89,86,104,86,586,493,104,580,298,67,760,434,698,185,535,607,409,141,614,523,327,321,227,503,68,788,400,705,208,70,172,779,236,24,696,468,55,681,498,157,433,441,572,389,187,168,117,235,52,695,638,82,700,708,341,535,51,178,540,700,153,222,82,64,655,617,632,131,500,596,300,389,232,670,432,551,364,616,675,72,223,464,230,648,513,504,503,488,50,319,504,550,338,69,328,388,674,427,72,129,769,464,694,126,271,788,244,794,141,631,577,788,698,346,606,399,726,795,73,552,385,637,36,1,123,637,718,761,549,316,232,752,30,635,784,102,486,537,360,412,510,759,143,81,325,499,454,421,219,111,587,313,160,650,64,651,532,772,100,317,664,158,664,782,619,759,634,447,749,143,76,47,511,166,77,414,800,669,126,108,16,659,285,345,175,520,268,422,157,412,266,498,123,719,152,61,424,482,628,487,612,628,608,721,464,390,91,666,331,342,550,98,245,742,671,10,110,53,168,688,534,259,736,22,302,49,776,635,245,222,542,736,395,618,452,228,401,373,441,135,6,64,766,617,746,618,593,522,29,595,500,427,479,379,678,139,689,610,200,746,690,521,760,488,674,431,792,486,258,213,263,131,337,633,646,191,239,765,403,187,540,480,752,277,248,2,348,399,228,548,440,232,703,389,130,673,233,293,348,313,35,772,197,176,716,707,254,646,356,449,101,411,715,542,124,240,257,90,418,772,7,629,760,119,796,784,220,233,32,458,16,539,276,292,499,76,311,348,390,28,201,116,711,684,458,299,24,666,186,545,696,392,218,439,552,277,233,620,294,322,263,640,244,78,149,371,209,569,786,518,318,3,606,88,25,364,409,745,708,245,419,153,702,285,765,392,424,548,486,695,192,458,478,677,616,400,518,467,383,757,477,191,518,121,3,363,91,349,184,22,320,383,796,192,436,737,688,650,472,675,243,531,298,131,101,443,268,99,679,66,669,450,152,233,30,64,56,495,333,317,359,180,492,634,613,632,410,438,403,604,632,145,48,382,260,587,508,800,416,741,184,706,331,446,3,194,70,598,285,226,527,654,422,641,584,228,286,223,752,250,550,733,136,656,637,634,718,132,611,310,452,504,601,337,297,331,62,172,702,445,146,262,1,494,341,223,308,159,295,87,118,687,681,687,776,702,26,581,296,268,90,283,600,346,586,497,599,359,777,613,198,179,439,153,163,767,20,524,592,265,160,702,748,243,668,16,632,477,615,769,786,709,769,17,604,13,427,544,213,788,484,271,190,410,748,701,501,383,771,586,572,420,713,86,722,168,639,770,696,43,100,236,172,557,664,22,80,719,668,608,259,208,111,744,262,688,657,112,279,144,290,215,504,462,290,733,584,748,594,451,72,330,369,616,694,582,607,204,756,194,509,303,609,797,778,178,254,791,6,756,9,80,273,597,324,329,491,533,334,257,533,277,424,248,430,563,240,622,118,113,72,4,174,591,335,601,437,491,486,717,651,71,491,257,656,354,448,531,260,701,36,357,776,246,216,567,347,207,90,583,509,391,748,599,239,190,333,518,272,309,446,84,672,267,253,513,255,576,172,462,750,532,42,698,491,104,792,165,440,730,468,272,533,12,576,793,192,30,539,738,667,110,70,682,165,478,319,178,478,109,776,184,711,28,736,286,30,745,232,772,5,86,286,424,636,162,484,44,449,45,665,111,406,56,446,241,26,578,657,306,301,459,212,243,592,147,774,307,609,219,424,626,610,65,696,657,275,167,408,110,786,685,679,459,97,433,358,103,479,309,627,451,588,504,272,125,393,763,508,727,340,92,792,337,271,797,2,713,762,445,124,641,435,604,262,312,796,603,30,622,564,345,774,771,315,630,284,696,498,338,195,332,23,718,280,415,652,136,637,690,49,162,624,195,68,732,532,724,551,180,358,452,633,76,776,628,442,131,376,482,43,730,441,304,394,207,232,190,121,132,167,394,184,344,436,598,645,171,690,577,546,286,414,651,334,400,122,596,457,129,420,253,436,273,607,5,237,33,200,748,246,271,769,563,431,189,168,696,470,331,768,29,397,119,294,193,147,355,380,645,360,654,64,712,205,441,725,329,608,674,440,139,227,619,235,11,150,83,364,555,567,666,382,362,648,33,638,456,392,519,622,549,23,172,108,2,54,208,315,318,451,20,152,25,288,22,293,532,237,505,704,429,520,474,76,646,499,538,742,478,653,794,112,246,694,761,584,205,463,344,17,322,790,789,648,24,77,274,591,300,468,526,324,800,137,169,330,531,398,260,62,357,738,94,642,150,773,471,724,391,632,495,439,471,761,7,616,134,682,733,137,53,779,20,568,770,474,265,632,367,281,765,262,507,711,145,164,391,740,388,368,530,689,23,749,379,204,296,408,261,503,249,499,749,18,617,220,309,283,280,566,156,180,775,318,290,604,85,22,199,147,34,220,428,154,142,51,272,143,314,696,627,276,708,77,470,617,111,240,343,460,536,772,536,127,768,550,664,705,488,472,376,626,527,536,759,595,470,9,276,514,347,264,530,545,480,151,494,784,580,532,586,685,71,354,485,666,74,190,511,246,748,394,632,449,237,260,625,188,13,751,265,517,621,8,768,606,459,433,23,455,746,328,460,510,615,16,97,261,579,678,693,155,415,780,201,544,58,384,412,21,117,37,238,152,782,632,415,43,679,123,47,430,543,492,543,799,182,174,14,288,557,542,124,368,579,734,201,719,56,236,726,350,236,427,386,123,768,600,589,776,755,661,792,549,5,672,129,48,22,668,586,171,134,390,338,245,598,160,58,142,517,392,481,375,372,65,263,558,705,776,620,53,750,95,592,620,122,548,596,433,165,314,631,198,400,670,409,10,58,146,250,317,131,180,315,448,459,743,283,433,563,200,346,754,506,665,697,451,256,696,214,34,741,392,723,145,777,774,143,463,685,244,11,348,720,208,390,665,467,61,512,4,724,56,665,575,789,163,305,234,597,572,713,387,52,262,32,12,627,574,22,356,465,454,651,747,206,605,192,130,746,515,436,135,614,632,103,412,193,157,474,353,59,305,75,180,564,564,700,503,492,262,684,425,484,648,700,298,571,409,715,635,626,121,409,698,519,8,70,393,732,231,626,616,400,213,670,405,227,658,201,754,470,638,19,158,72,122,316,601,185,645,613,292,169,287,525,669,25,136,436,6,232,257,123,383,310,9,640,422,515,96,5,541,240,550,522,259,283,348,493,152,422,705,176,797,17,373,402,304,538,536,83,307,739,11,563,454,171,525,307,711,274,702,146,568,505,382,80,536,287,110,269,743,580,13,586,6,72,539,454,211,620,184,673,432,559,101,796,605,721,449,661,120,658,12,206,451,83,486,711,765,434,560,734,166,305,73,789,31,400,273,619,6,749,40,480,509,202,687,116,132,166,133,72,601,545,426,315,542,220,574,141,178,406,482,766,533,175,181,783,104,231,87,767,41,31,8,46,570,118,297,445,347,44,473,10,746,481,120,151,585,214,294,100,471,649,164,399,532,156,753,442,513,47,461,484,508,64,88,77,487,81,339,277,450,1,701,509,747,432,86,356,388,383,638,394,556,653,790,367,323,314,541,404,138,358,595,728,607,370,632,603,772,605,493,158,697,583,241,383,540,48,228,448,335,121,134,449,17,416,440,480,770,295,249,415,323,174,745,29,338,467,200,90,497,536,567,182,224,668,757,594,125,223,2,461,458,578,734,167,518,420,522,640,497,197,261,633,44,5,623,561,533,549,72,552,782,708,241,319,87,98,169,628,622,607,80,489,565,188,358,30,363,183,556,337,656,82,577,324,69,109,421,662,680,70,24,519,283,191,347,503,222,759,333,775,399,559,110,662,528,517,414,548,64,507,670,562,607,688,749,254,110,708,203,10,236,728,184,725,697,203,213,640,245,509,673,489,416,366,764,530,539,511,518,763,613,590,768,162,190,413,745,489,295,524,513,623,31,153,584,20,38,358,543,728,604,498,741,796,289,286,794,63,662,648,30,513,26,466,306,643,397,315,533,387,336,611,71,675,226,75,168,706,451,146,505,513,403,440,25,414,594,477,136,219,481,578,422,696,511,741,468,595,428,168,657,14,137,363,573,104,693,652,216,129,528,45,707,121,602,269,765,401,755,621,486,712,732,619,574,574,564,393,646,788,155,198,541,168,338,770,611,636,152,222,184,175,461,537,701,450,689,595,113,595,548,108,308,772,647,229,326,21,217,220,392,196,762,723,537,563,11,138,505,769,11,799,232,302,186,340,583,378,408,744,789,294,133,604,626,529,162,558,606,699,462,96,794,645,41,401,325,269,660,513,799,277,718,721,584,540,759,384,1,99,463,142,169,553,182,315,320,749,109,200,710,146,755,531,380,789,200,415,257,312,749,297,373,698,513,306,216,27,228,283,715,699,150,643,717,91,535,203,318,442,424,209,574,184,296,791,334,726,119,92,653,594,54,160,475,110,36,260,120,73,641,295,165,324,461,41,705,766,776,490,396,310,371,139,262,687,237,298,144,230,694,490,521,157,239,680,529,339,695,197,136,552,494,514,111,540,340,606,229,560,649,474,714,291,366,340,478,661,546,494,674,199,101,167,117,87,472,511,119,39,90,567,456,278,779,590,137,613,331,708,121,499,506,601,664,479,601,750,422,236,199,641,516,791,36,437,81,418,17,295,781,364,749,440,728,437,728,617,243,349,306,409,605,773,603,425,54,748,532,279,798,562,444,581,662,56,83,658,189,732,634,638,435,416,80,554,280,355,629,53,141,262,713,223,401,40,556,648,580,232,31,209,230,777,513,536,728,552,498,224,729,743,307,454,745,197,579,139,104,482,546,464,279,446,400,500,85,282,13,312,354,725,122,410,190,175,534,348,170,201,289,317,37,577,348,221,783,473,38,61,168,80,287,412,113,455,71,762,617,61,734,567,592,18,421,340,134,262,475,304,300,89,320,491,737,716,405,517,773,542,793,158,248,111,652,183,571,383,366,751,77,559,575,327,174,638,320,669,350,268,336,691,574,474,303,680,493,38,542,316,683,242,348,688,568,477,9,611,213,40,37,309,289,306,48,422,764,635,651,343,646,131,437,263,576,74,46,630,169,593,791,676,33,471,175,657,424,572,310,222,703,128,588,618,677,324,81,214,762,359,6,800,318,681,10,202,114,235,221,595,213,651,160,187,551,491,594,771,296,266,563,778,121,553,515,208,89,167,738,405,488,676,113,602,742,384,559,94,596,347,380,609,593,470,601,771,701,272,357,484,760,73,704,69,547,289,682,229,317,345,195,37,134,304,524,195,30,742,356,33,326,28,427,702,445,208,418,314,707,4,584,598,88,791,605,369,701,682,257,715,657,700,116,164,436,429,23,477,678,157,169,533,40,652,234,364,25,155,475,578,665,553,603,55,552,726,714,332,775,386,8,96,597,270,245,596,722,377,178,742,478,355,62,408,634,493,665,297,677,693,516,345,543,221,254,649,168,548,167,568,353,235,127,38,681,465,486,563,512,566,189,512,742,442,387,172,572,701,88,215,609,352,573,673,21,34,113,779,184,675,724,51,683,99,230,123,621,291,295,259,414,66,536,585,798,352,248,463,142,542,167,468,269,314,614,664,283,22,500,252,56,690,305,223,293,684,733,321,769,198,760,194,556,319,675,259,646,343,349,707,144,238,550,258,393,709,255,416,497,571,519,222,232,528,734,666,623,292,484,502,709,536,793,466,490,235,382,652,670,381,466,230,290,79,373,95,149,287,584,727,535,143,650,175,488,95,219,358,265,141,603,732,569,731,42,593,440,744,585,454,166,500,407,154,324,479,436,781,273,138,417,223,269,20,669,625,152,221,488,673,755,197,514,689,541,205,11,289,182,20,4,559,30,250,716,157,502,800,771,490,541,260,394,310,83,616,128,610,120,300,421,173,429,78,409,247,305,80,124,384,708,241,495,649,390,593,209,465,760,592,418,152,121,655,259,606,585,301,307,740,8,586,82,200,727,678,384,76,725,610,605,464,2,477,362,722,542,599,486,148,714,49,273,21,517,649,332,117,751,193,630,341,168,633,207,692,689,367,439,18,489,453,110,399,48,730,21,588,646,718,715,584,396,225,208,355,353,628,325,381,709,198,681,279,504,23,732,527,219,264,734,743,365,567,48,31,430,614,368,277,222,724,640,459,766,450,480,736,653,686,622,437,11,442,364,424,24,582,505,475,373,336,469,749,769,474,481,542,636,355,699,143,454,395,677,799,480,434,319,398,393,633,263,732,545,479,255,74,552,708,70,374,127,9,380,258,645,556,706,14,26,431,278,504,286,305,218,226,50,595,174,523,597,403,144,788,231,339,674,155,616,595,483,226,537,401,243,264,121,335,275,77,584,620,769,370,230,200,159,566,724,611,461,633,145,574,681,251,669,440,693,381,88,17,624,605,323,586,570,541,637,481,756,125,550,184,156,763,510,174,660,761,454,452,668,86,93,312,658,339,67,524,504,782,408,384,621,777,765,626,337,419,657,228,5,28,660,405,359,597,614,549,441,621,264,340,635,164,473,3,715,346,697,465,491,112,712,222,570,548,519,203,312,600,85,150,710,428,402,257,706,286,478,139,494,464,218,693,202,193,517,669,532,594,575,549,174,577,488,653,503,112,97,659,463,606,489,217,215,203,352,158,333,248,6,770,115,676,156,389,585,367,65,520,141,793,469,714,161,451,472,363,420,491,363,12,150,404,589,651,152,155,478,330,72,673,94,232,584,615,142,230,56,492,781,99,438,17,795,542,644,468,664,122,161,599,37,660,653,153,1,46,649,762,108,391,371,411,6,287,109,603,400,310,727,218,201,77,143,728,497,67,87,598,40,568,718,370,335,557,500,527,69,576,10,202,234,595,142,548,606,293,578,94,514,663,422,215,21,424,24,784,599,791,506,615,616,327,459,94,361,85,11,372,25,451,27,489,344,368,377,510,742,220,711,466,708,135,261,165,49,690,721,791,781,668,685,9,536,485,504,185,435,142,338,490,157,117,316,729,694,732,756,615,798,770,284,213,22,264,340,482,509,365,794,687,435,144,304,282,376,308,629,165,493,182,265,239,209,56,749,504,580,569,383,513,518,793,225,265,440,312,243,432,505,23,563,54,777,53,547,348,648,178,706,64,247,175,208,485,21,106,462,648,34,677,26,746,734,639,374,300,42,441,66,301,165,306,28,46,591,73,102,493,712,385,191,204,337,279,583,778,777,205,159,327,528,66,549,4,742,502,539,768,716,425,513,443,161,700,437,757,709,366,345,175,248,191,108,168,59,624,142,576,621,415,800,311,398,270,224,109,606,380,624,451,318,234,752,184,621,23,126,45,171,483,188,192,216,110,41,403,469,696,581,517,577,226,689,22,572,11,747,263,230,531,789,247,224,186,175,710,617,257,599,628,129,327,271,386,296,428,342,751,511,177,556,187,69,468,82,710,122,535,38,560,382,281,10,506,594,699,30,579,661,92,480,556,711,476,18,19,520,475,723,250,505,601,35,384,665,247,67,293,584,244,721,458,326,336,15,686,532,363,93,337,401,678,313,435,317,736,389,213,664,505,288,278,483,178,554,374,413,233,548,373,742,512,492,211,127,374,484,49,454,44,556,590,797,1,386,171,643,437,168,358,441,104,541,129,477,666,481,411,81,140,181,660,276,509,87,45,39,557,169,101,520,412,619,380,537,555,699,274,57,665,155,712,777,70,74,445,487,371,616,657,565,62,54,612,82,681,18,246,63,403,510,136,506,189,602,537,613,134,132,138,63,718,158,249,745,597,167,72,513,251,703,214,233,353,295,291,384,646,509,560,679,330,291,508,796,269,249,7,353,144,413,689,21,498,241,443,25,19,276,740,555,20,678,460,525,499,584,147,606,274,216,186,287,17,472,735,174,366,488,420,205,715,262,553,667,679,84,524,409,226,593,719,517,156,317,369,673,86,473,466,332,207,643,83,327,423,29,403,240,638,71,786,553,85,95,208,145,203,359,430,105,672,542,299,623,309,580,615,773,648,26,354,234,219,382,61,223,622,722,566,450,479,342,623,469,16,552,744,439,736,394,767,681,143,251,374,9,29,91,652,345,747,139,449,24,376,137,22,551,292,215,682,196,335,341,253,721,474,641,623,589,164,669,1,537,589,8,338,531,438,770,706,477,189,588,497,470,740,676,448,511,363,332,781,630,464,644,442,541,693,106,359,659,377,64,82,409,156,229,733,749,702,697,487,561,224,253,624,548,385,623,217,391,129,465,705,248,128,739,776,89,479,259,654,681,157,627,436,777,762,658,121,695,55,640,733,693,434,670,352,322,45,394,387,63,488,774,676,202,737,18,229,549,58,748,518,367,274,470,645,553,329,15,516,145,799,183,162,105,373,559,608,656,10,181,444,231,318,555,664,716,594,593,371,641,164,389,333,741,630,745,743,249,327,636,224,539,280,126,312,653,743,16,463,622,758,721,742,351,613,705,251,382,786,96,720,301,671,238,101,747,299,780,280,409,662,761,619,181,512,85,733,609,426,97,655,764,755,348,511,71,347,326,591,320,323,191,702,489,745,647,460,65,495,255,506,361,340,678,199,287,793,316,211,709,604,450,606,666,639,247,297,543,34,315,210,338,35,238,635,21,164,688,68,295,100,34,587,489,579,419,146,89,353,595,56,537,447,755,574,616,92,162,66,167,24,352,550,436,116,109,9,17,750,777,619,61,456,341,429,185,225,208,750,227,794,666,718,413,593,500,173,6,520,93,428,127,319,85,649,646,276,572,614,509,649,306,195,579,221,408,638,153,144,589,441,93,514,337,563,241,116,709,525,692,581,680,613,455,501,218,765,648,517,667,500,89,691,587,554,25,257,619,64,745,334,794,501,263,187,696,425,533,390,774,60,690,689,323,111,543,60,719,32,154,613,138,433,421,238,308,290,63,662,654,561,169,189,215,416,225,195,239,654,393,681,631,60,736,622,302,40,647,50,692,596,156,790,681,223,1,184,45,457,213,314,257,691,505,315,356,348,427,28,182,580,141,764,280,779,382,314,137,754,127,121,41,759,590,630,24,637,269,691,438,33,91,335,484,260,89,458,257,487,677,708,205,681,609,382,41,715,460,727,116,619,103,143,622,427,208,263,471,362,41,285,495,520,17,83,503,6,521,264,366,67,303,221,532,287,741,337,714,282,714,355,751,309,127,502,355,142,674,295,486,712,309,728,504,672,279,424,570,183,329,631,299,526,681,133,299,4,505,563,795,570,472,384,666,110,743,236,744,130,388,632,357,213,721,610,177,231,13,588,77,601,601,757,56,202,435,190,594,538,797,38,732,713,214,428,757,344,95,755,477,165,182,312,180,83,573,221,282,735,147,225,336,650,57,708,373,597,45,582,105,255,17,680,269,489,452,9,288,273,199,297,770,249,696,585,467,512,25,455,627,38,681,37,643,12,585,354,770,465,503,127,272,53,309,571,526,536,2,213,251,635,223,208,343,92,522,201,290,350,677,194,92,94,719,762,678,381,233,497,319,316,17,455,167,26,585,349,383,120,528,434,230,436,551,710,412,496,556,346,385,651,257,492,149,581,389,446,441,479,217,47,460,120,379,128,110,720,77,464,32,327,142,447,385,798,383,77,369,532,702,602,80,201,77,583,734,701,107,115,284,624,185,414,745,131,53,648,293,693,193,498,145,583,476,347,204,727,167,227,278,135,640,683,335,790,425,369,791,4,257,119,719,338,297,668,54,799,415,385,396,363,165,453,434,694,346,136,327,161,31,394,331,331,50,747,734,84,149,428,192,284,487,684,786,483,73,267,787,778,121,617,227,432,185,199,67,54,648,580,210,378,199,256,80,798,308,668,573,449,49,566,473,387,445,432,613,741,569,73,480,326,451,290,170,646,29,506,4,261,70,785,685,612,287,263,709,162,294,668,428,671,381,17,162,763,67,357,552,310,569,440,221,401,221,170,321,491,657,220,757,709,628,365,152,733,711,125,202,309,616,397,651,108,569,795,219,738,473,457,443,600,41,758,618,525,743,419,8,161,757,111,86,468,18,346,115,455,159,356,767,377,250,365,762,234,293,182,132,154,159,30,542,233,41,709,231,120,1,363,383,742,585,81,7,116,544,54,126,384,71,58,452,172,604,798,793,247,65,640,61,385,373,642,49,619,377,484,596,244,587,356,710,764,525,740,424,323,190,131,89,106,511,289,153,784,206,446,552,277,525,379,166,345,635,599,116,61,281,242,721,447,197,300,445,481,353,230,281,131,460,415,292,355,231,311,734,3,80,143,263,226,329,133,287,544,497,91,743,350,73,113,222,187,15,229,164,471,709,313,346,306,746,556,31,461,351,606,307,391,34,335,470,96,309,544,456,568,151,16,202,112,393,639,667,582,73,621,795,732,377,635,651,722,408,264,234,582,327,500,56,730,484,96,501,77,113,10,1,543,461,724,29,401,505,766,8,130,51,710,130,146,701,462,780,289,630,245,229,624,639,379,45,766,342,192,260,619,381,741,234,503,691,297,160,3,281,748,549,77,589,78,377,279,465,16,701,1,36,721,176,553,199,241,114,657,280,209,707,376,793,367,67,702,265,269,563,164,585,587,338,745,599,455,160,141,21,483,94,656,738,190,331,467,671,632,519,789,266,305,50,438,165,522,620,662,175,354,662,342,425,761,719,212,305,143,791,530,457,741,207,752,112,346,470,140,263,206,44,456,460,162,113,323,577,372,677,638,325,486,393,791,569,632,348,496,603,584,638,488,749,24,272,703,430,679,657,406,703,533,417,108,702,98,192,257,461,463,655,597,715,507,780,137,25,486,697,571,661,241,22,77,161,666,705,223,796,451,540,527,679,779,390,671,96,51,703,718,745,633,168,445,65,703,479,138,553,5,614,55,767,41,637,707,325,109,610,206,698,112,727,793,511,50,539,259,114,531,46,748,629,404,337,404,359,84,706,732,265,19,707,322,697,754,564,40,601,47,307,686,264,716,770,786,103,72,352,534,564,324,621,473,177,414,618,348,669,792,725,221,121,210,16,734,483,170,571,190,605,674,404,93,103,121,157,572,735,271,85,186,167,4,28,87,61,473,371,275,612,109,568,399,57,544,749,425,606,627,306,195,785,740,517,381,53,213,392,565,743,549,666,77,521,341,475,740,121,131,76,283,538,177,619,144,393,671,538,101,424,619,761,697,757,631,454,300,371,546,515,31,287,236,495,81,347,789,778,194,5,30,149,786,64,326,110,322,777,109,311,496,578,436,528,30,169,185,567,748,129,126,654,312,487,130,596,356,93,294,73,431,609,9,270,794,470,330,33,675,537,556,452,332,524,268,727,436,621,396,344,763,223,747,585,706,511,777,361,136,495,358,312,77,333,419,535,657,508,671,196,597,537,122,193,215,710,245,110,314,513,750,777,91,173,711,788,91,103,351,462,571,433,535,535,346,297,110,272,473,690,35,183,726,681,281,430,627,720,365,85,15,613,609,42,266,779,148,175,773,351,710,675,415,355,599,102,504,725,776,153,144,632,664,410,424,169,71,523,734,522,406,12,789,313,259,539,330,761,240,538,638,263,220,328,754,325,520,229,581,721,403,530,184,462,60,45,41,313,486,504,442,564,782,211,714,125,150,60,217,55,381,757,296,95,291,381,150,471,8,404,707,221,781,283,783,52,305,656,443,729,404,629,581,462,183,362,720,785,312,365,633,741,249,320,609,519,313,162,105,793,441,243,688,25,440,84,439,490,85,355,92,9,755,578,609,664,495,177,645,597,395,270,424,611,678,411,171,479,320,151,653,43,217,546,78,101,786,157,270,560,362,38,686,73,513,95,268,626,184,328,171,73,525,223,648,593,642,486,356,455,54,380,800,141,234,1,187,705,253,438,662,326,495,761,335,377,480,12,40,636,656,591,416,397,32,320,471,271,47,641,686,799,573,113,324,351,586,464,505,45,727,319,333,396,323,284,1,633,142,425,404,54,249,38,262,225,674,529,23,93,299,44,583,327,595,278,23,737,795,527,518,457,162,632,117,194,648,175,194,265,525,662,79,576,241,621,635,581,53,594,486,539,632,391,369,767,794,331,763,371,475,62,420,629,316,353,684,552,28,338,436,169,731,211,155,698,26,100,129,217,151,483,742,73,244,754,202,359,80,304,46,181,684,381,689,113,7,282,52,798,545,389,725,313,506,192,726,676,690,43,278,253,138,516,309,775,33,173,532,799,439,485,178,679,12,460,655,190,769,675,619,132,21,680,295,569,424,317,418,158,411,450,92,466,428,661,405,117,189,344,77,775,781,298,485,393,221,171,380,346,44,796,179,218,282,91,488,745,551,10,509,552,19,457,785,662,703,342,324,339,42,723,535,671,404,319,393,155,285,154,474,230,422,5,74,672,78,574,346,713,373,743,457,66,28,608,183,10,321,711,324,257,102,158,433,103,459,708,444,61,174,153,167,450,241,30,370,438,435,657,667,633,404,532,356,300,20,39,300,174,276,488,211,543,595,505,186,255,273,537,576,79,430,264,677,238,363,359,713,732,615,724,77,441,770,337,752,646,701,670,530,258,790,249,83,13,175,68,244,647,584,414,83,81,223,135,498,458,86,672,401,178,460,679,686,585,737,670,747,16,789,549,103,230,681,410,610,683,668,415,733,95,302,147,535,163,735,630,112,182,496,585,680,280,160,394,256,425,783,315,759,682,126,252,493,410,171,11,66,729,56,42,279,423,709,88,458,325,528,149,477,434,347,162,208,174,165,541,609,793,334,488,434,276,310,643,130,158,350,492,369,311,741,5,736,319,395,461,622,631,176,484,187,574,725,267,679,596,697,96,467,89,348,325,446,718,671,410,72,50,512,445,145,5,161,400,762,103,578,274,33,569,417,387,520,538,128,4,751,298,446,307,180,233,795,530,57,472,55,545,605,630,243,318,128,739,654,11,675,351,776,455,517,331,257,594,742,38,794,333,262,624,530,662,422,265,457,271,709,594,352,568,515,522,565,655,768,465,170,470,29,135,319,588,536,525,370,241,275,706,165,518,718,742,119,489,423,505,584,252,448,252,312,383,632,334,392,624,144,175,695,49,646,639,197,417,412,319,115,320,337,206,447,15,773,780,747,301,761,153,470,26,620,534,769,566,766,258,394,97,367,509,19,476,160,135,92,646,111,65,35,383,350,202,170,552,269,34,688,448,506,73,533,743,455,224,377,605,403,646,157,450,575,27,736,215,137,415,98,411,339,691,68,302,604,150,228,273,708,552,452,163,748,137,99,740,435,538,610,52,505,26,319,403,478,617,348,290,195,167,665,544,102,213,276,653,745,754,303,362,748,62,329,278,173,473,2,177,782,228,378,411,14,574,594,84,110,359,713,93,524,479,223,117,234,135,149,636,327,798,137,83,35,228,253,217,703,793,304,366,154,670,387,178,628,82,148,197,749,661,261,488,486,7,726,698,221,73,709,635,532,474,84,236,363,282,34,204,160,297,783,763,117,712,603,185,137,502,327,742,733,531,178,131,303,447,156,623,449,27,646,394,466,518,206,373,514,384,630,591,434,201,29,632,609,610,644,560,783,138,138,599,764,481,206,526,393,103,179,404,340,93,246,9,192,130,377,142,458,310,603,66,115,313,444,581,60,12,732,727,196,366,92,312,140,159,219,361,754,383,377,425,280,335,663,280,797,78,371,535,673,60,271,581,517,569,170,546,360,614,709,558,42,514,287,233,107,589,375,788,172,423,560,686,267,497,519,535,75,234,254,80,9,274,180,696,134,73,329,687,67,240,733,565,95,518,369,458,251,395,708,143,661,319,694,483,719,483,8,422,200,790,472,185,192,472,168,571,632,681,791,492,623,714,166,204,357,698,628,603,666,601,256,730,751,423,77,616,258,37,120,645,630,434,323,466,136,494,45,750,217,633,662,729,138,308,382,659,378,62,422,348,362,343,333,437,728,479,595,221,70,503,441,148,339,798,253,763,255,628,385,241,11,441,100,310,22,366,583,426,800,786,137,461,41,357,137,96,18,167,458,738,185,729,649,115,417,442,616,116,423,298,486,548,652,649,707,515,593,184,287,625,437,150,699,398,57,579,118,667,571,479,208,119,253,459,618,66,158,38,738,477,350,16,570,359,254,169,785,576,221,466,584,744,59,42,126,447,120,369,499,518,277,679,551,60,657,237,794,577,492,34,557,54,454,294,63,602,671,729,784,621,312,316,256,527,656,750,784,768,40,271,63,705,766,575,45,81,532,703,699,48,361,302,39,639,413,492,51,509,721,729,30,330,228,534,201,358,566,514,179,721,391,189,348,524,760,359,260,342,456,545,11,143,631,138,274,248,453,162,88,624,50,713,477,119,127,384,769,557,331,518,549,242,663,667,232,199,129,511,298,331,683,371,588,574,84,630,588,97,412,40,236,691,612,105,459,52,555,154,522,4,401,218,104,259,214,649,197,114,219,487,449,560,255,501,220,637,578,498,759,218,484,798,305,742,677,409,746,449,6,36,578,619,582,798,442,196,326,7,337,685,68,63,359,709,546,423,189,140,159,94,209,323,347,356,389,649,375,697,312,702,594,670,619,546,748,498,253,405,5,597,718,344,62,263,62,74,726,585,493,395,141,538,412,508,131,762,618,28,792,41,535,299,237,104,611,457,417,438,303,246,693,531,794,275,455,511,708,223,697,667,686,346,394,70,470,229,186,128,734,799,458,713,517,232,601,162,12,32,711,650,50,743,244,673,695,670,737,295,315,228,141,285,350,121,760,194,417,638,34,566,707,338,748,313,324,149,596,140,164,615,252,78,164,72,388,127,483,473,490,799,545,249,752,111,383,456,405,430,731,135,505,508,215,245,509,633,659,178,416,262,429,798,322,578,647,185,611,653,448,292,292,7,216,30,356,465,527,391,643,106,646,96,545,370,412,520,127,169,177,159,219,656,485,229,791,6,537,698,371,171,652,159,333,511,414,403,359,99,48,374,640,22,672,137,376,600,336,203,464,713,32,732,391,650,686,508,573,538,220,107,50,569,649,650,295,295,213,24,59,485,736,213,206,626,11,66,192,782,501,702,178,697,286,489,226,692,230,99,626,766,46,556,34,471,85,613,240,319,251,493,446,343,609,708,363,382,5,523,151,276,745,609,643,153,45,102,142,46,399,122,664,82,177,157,577,677,82,560,490,327,242,466,690,57,657,67,185,602,528,68,575,106,750,180,453,521,715,115,521,632,679,385,13,790,99,158,209,227,670,107,211,31,408,199,53,491,402,178,502,358,42,621,374,560,194,279,214,361,410,496,501,50,368,120,435,234,390,751,432,465,411,726,365,423,15,12,169,333,130,465,356,674,277,742,94,70,455,490,24,153,88,701,688,60,745,767,648,270,792,369,544,527,743,753,406,479,693,385,396,255,35,225,225,430,79,719,726,588,251,621,457,793,775,634,124,566,497,758,206,322,347,162,703,285,68,732,528,39,524,710,224,257,499,512,207,458,282,520,509,674,576,672,363,41,741,679,503,608,426,349,3,390,109,67,335,731,432,599,441,383,722,731,99,307,20,79,12,214,436,689,213,40,116,611,796,489,788,452,611,570,370,500,457,442,48,788,686,297,269,450,115,583,265,192,119,437,324,686,410,242,95,106,636,734,665,278,382,217,658,369,414,644,363,411,94,318,674,85,414,423,793,317,668,543,591,181,474,711,485,349,343,350,89,243,404,484,141,377,463,217,705,558,362,734,563,626,260,626,581,486,573,181,566,8,182,199,646,250,14,617,53,700,773,410,260,748,699,26,338,108,241,201,799,187,421,776,428,249,281,598,183,647,525,115,34,3,319,351,492,655,17,251,86,523,258,774,478,245,307,160,294,79,66,457,14,568,369,98,564,592,447,458,730,440,492,513,287,14,473,359,707,628,5,669,742,490,112,642,585,14,154,406,427,354,228,569,12,37,204,652,269,535,725,46,620,121,92,319,715,9,386,575,425,553,104,207,39,217,621,46,516,759,530,412,95,357,725,281,123,66,600,582,405,718,154,738,495,106,379,301,456,660,572,167,768,526,572,625,727,568,603,714,782,144,729,274,580,760,535,73,153,303,723,560,622,53,688,358,257,427,779,715,212,719,37,95,646,739,223,515,504,743,152,694,9,313,465,56,792,187,232,41,264,172,95,746,566,684,213,602,612,92,746,345,273,506,543,743,61,200,83,101,360,710,518,402,755,690,24,494,541,718,554,441,710,505,570,500,175,691,619,94,758,93,474,183,317,533,168,447,163,189,310,663,169,501,355,510,110,123,176,436,113,17,379,633,85,310,6,110,695,778,528,594,665,654,505,357,410,576,354,647,314,610,714,441,409,564,465,186,504,372,23,458,566,516,61,361,211,739,193,152,48,433,422,86,683,15,329,291,70,571,235,159,480,119,333,523,186,35,14,6,371,125,175,592,74,231,558,777,770,480,13,722,600,264,395,330,174,800,360,145,547,550,453,487,791,636,321,653,330,770,444,482,541,86,566,422,623,154,528,121,384,749,329,700,433,175,481,526,640,193,632,463,431,417,238,31,29,369,356,735,587,689,665,430,152,223,142,172,292,157,33,217,655,170,52,790,57,70,582,642,131,370,663,125,524,588,712,743,660,214,440,1,59,240,647,714,706,184,245,450,424,112,547,585,461,151,48,64,626,525,124,742,53,243,231,27,376,391,625,447,58,395,219,51,252,575,68,278,125,417,781,200,125,115,660,169,668,180,507,538,730,516,449,58,792,708,134,105,725,594,683,103,401,784,47,277,44,318,114,498,199,538,20,286,769,774,342,793,346,65,215,324,467,491,727,94,298,677,502,583,321,653,84,160,791,37,690,519,205,269,111,254,770,163,236,292,150,105,7,250,233,670,354,254,603,770,444,242,493,438,309,597,798,728,302,424,462,202,294,265,61,684,157,250,12,732,627,154,730,380,73,74,679,459,222,744,788,585,242,278,63,55,549,755,650,19,151,736,660,671,457,571,158,155,634,6,71,645,619,448,271,703,698,362,726,104,329,322,124,32,87,234,34,584,676,545,743,798,753,200,43,740,509,509,622,282,552,738,209,606,50,86,499,402,412,122,468,469,517,12,245,263,781,782,500,329,84,319,83,153,539,768,210,601,224,47,175,169,517,238,140,743,426,60,232,597,781,794,227,498,784,166,61,382,50,482,407,570,691,461,464,740,116,616,296,478,372,593,159,520,371,138,342,96,401,50,44,552,367,778,321,703,652,48,182,133,72,262,457,539,259,683,764,159,574,640,783,691,23,451,256,471,656,534,529,73,425,600,65,747,256,106,80,764,183,394,702,796,493,122,76,204,2,633,281,394,23,648,5,344,491,485,560,630,446,274,347,610,752,302,773,670,578,282,686,201,659,596,471,163,611,574,638,333,210,87,293,613,769,768,364,109,270,279,49,581,123,574,310,235,648,52,378,577,339,794,125,102,702,174,191,410,72,466,321,286,721,325,290,688,26,232,610,722,354,569,225,356,361,410,384,68,623,234,606,468,149,10,795,499,442,600,696,769,670,758,243,255,225,227,238,139,676,352,297,391,581,459,354,723,70,390,219,77,167,400,243,599,710,746,714,304,325,210,352,56,259,522,438,400,641,433,683,214,221,200,607,620,249,781,499,50,340,770,709,38,750,262,87,554,296,730,200,637,385,412,89,63,217,558,168,369,784,719,791,114,71,576,454,482,92,671,371,1,209,110,800,335,166,716,236,77,281,410,407,90,268,374,673,566,158,162,331,578,496,509,436,221,320,680,444,551,784,225,196,288,543,426,426,232,237,386,752,800,667,42,373,487,328,640,602,285,116,550,61,611,735,699,480,440,266,640,643,28,115,723,260,783,156,438,101,625,773,744,645,131,428,458,772,580,531,122,450,244,729,666,352,244,383,169,445,643,515,712,761,225,711,181,789,142,586,722,239,394,204,30,553,118,558,474,66,625,687,548,443,507,271,286,658,501,334,39,521,254,333,32,544,438,362,711,309,157,71,734,426,179,68,196,734,153,319,762,305,686,666,62,451,626,404,274,661,166,302,213,70,521,198,40,406,27,126,521,230,732,117,26,20,12,107,122,130,236,193,234,783,571,374,712,412,473,778,246,423,711,157,371,338,324,48,416,221,80,513,187,614,491,690,486,175,21,195,448,407,559,50,586,350,760,481,34,100,368,495,362,362,120,669,97,719,783,265,40,787,341,725,541,279,682,576,706,281,46,618,150,219,514,660,602,732,709,61,716,93,759,101,398,637,57,76,31,123,106,435,800,314,202,248,591,439,185,542,334,468,759,674,316,688,197,517,346,427,162,680,294,485,270,490,418,31,266,140,461,664,405,780,264,624,239,268,433,552,120,747,554,510,496,521,690,532,568,551,458,713,719,420,400,286,149,576,358,146,491,187,203,772,688,790,768,663,324,239,483,72,615,777,182,313,89,353,536,745,123,600,746,408,12,559,266,486,204,453,282,52,60,603,313,289,91,111,712,557,361,739,677,89,166,566,274,483,626,168,526,269,238,346,378,182,249,363,500,191,179,539,126,679,285,426,631,653,374,665,704,724,446,230,23,729,149,564,382,446,603,224,148,386,657,779,250,453,54,438,270,263,618,544,722,777,302,714,421,650,353,82,328,650,227,666,25,42,116,673,186,136,436,647,362,454,612,557,298,419,131,786,408,768,593,790,374,28,687,89,67,406,796,796,448,337,280,797,331,554,387,799,486,355,349,351,560,731,199,446,426,274,640,125,402,776,648,251,330,318,416,345,465,307,263,85,328,199,701,81,493,251,642,780,354,205,566,326,678,703,250,32,666,720,461,281,220,129,143,625,782,81,225,40,207,608,546,95,640,526,114,277,31,187,17,682,654,712,31,94,684,52,349,625,186,767,74,740,246,105,614,118,546,403,626,552,221,668,45,536,104,644,375,360,545,716,528,631,394,18,376,581,514,376,496,531,586,669,663,96,96,2,365,76,38,38,595,343,571,297,552,290,96,203,44,204,307,140,287,533,566,397,129,509,296,461,83,324,42,428,148,395,154,714,484,497,506,744,388,663,233,101,51,27,744,193,753,159,53,541,638,226,754,183,58,100,574,529,70,70,218,746,97,263,132,547,779,519,510,731,5,358,711,626,46,709,192,8,230,675,359,29,13,128,30,18,707,796,484,70,617,183,378,633,350,626,190,107,418,524,18,573,214,550,53,526,473,190,296,30,11,310,361,110,492,653,506,252,572,483,570,458,636,729,10,439,395,302,200,36,585,514,406,144,695,405,691,155,116,328,32,613,256,698,315,366,443,171,390,759,645,59,544,223,447,522,490,38,296,185,610,140,640,711,586,402,200,501,705,183,543,609,392,731,293,333,189,351,666,792,770,737,62,546,278,643,114,716,474,133,181,629,684,613,295,285,174,709,393,260,31,516,218,491,512,482,282,273,271,287,233,342,558,764,487,218,28,184,661,510,666,51,626,448,646,685,510,482,162,551,538,548,621,480,517,388,392,184,543,644,401,464,712,611,42,358,128,545,210,732,744,255,138,370,383,540,720,422,581,632,134,346,731,211,427,173,736,302,160,639,244,520,515,304,567,161,374,129,777,249,504,209,683,401,618,576,412,615,490,174,796,381,154,796,716,307,377,169,299,775,296,213,153,539,645,321,310,270,466,43,642,672,174,405,670,146,410,191,9,515,116,743,515,115,158,79,397,2,727,438,6,81,448,252,622,735,791,577,197,300,414,166,363,216,84,458,449,260,314,525,102,718,142,431,218,56,274,145,606,194,5,786,241,554,40,690,371,274,377,306,356,761,378,48,548,671,618,686,212,549,426,620,371,266,504,424,353,78,86,260,479,529,195,415,76,564,160,633,328,694,747,50,147,759,6,683,717,119,208,355,183,407,618,346,432,21,658,272,472,787,10,678,80,785,657,27,503,109,232,495,141,41,589,259,498,516,706,21,326,415,518,743,202,344,410,505,317,465,668,265,671,265,654,441,593,224,495,680,178,535,160,502,2,45,319,483,705,706,270,464,752,214,684,444,749,10,186,231,218,220,662,530,535,302,354,571,386,64,541,164,381,304,392,236,423,224,193,116,96,79,682,314,553,190,514,768,224,619,42,6,391,152,512,490,606,612,198,462,739,655,795,785,120,90,576,435,124,4,371,52,719,237,246,213,274,309,168,629,35,605,234,372,196,3,58,563,85,233,634,560,116,495,649,269,579,403,456,137,353,695,309,5,46,250,146,703,203,61,734,217,182,414,602,51,465,543,4,555,508,671,478,67,405,254,776,730,318,477,768,624,438,507,232,165,541,344,318,442,148,148,389,494,633,48,666,737,78,650,575,564,595,228,18,293,774,30,278,374,41,150,104,454,475,78,266,182,348,325,26,260,461,700,443,242,44,305,490,480,123,678,73,236,538,218,598,632,391,429,180,195,644,672,320,621,656,530,412,790,331,291,230,767,662,787,641,679,15,771,586,270,376,561,579,213,593,31,138,570,56,525,290,383,335,505,40,643,437,165,606,647,74,48,482,106,271,187,407,235,66,772,634,205,197,109,13,429,312,757,142,397,121,700,544,556,554,579,192,202,490,425,688,391,473,302];
X=[253355967,10251111,272311899,213052247,46690406,221355656,130046935,149396632,697901040,63425679,1000000000,285825511,1000000000,225208021,309094470,117837651,986720888,90137300,627711884,787578858,8674180,253671768,625791388,352946143,829900245,24212425,92382204,8075221,206055683,229364466,300842212,1000000000,182308817,32049423,294777983,639613954,42958407,28423512,1000000000,358690112,53140197,513064018,30483515,1000000000,22685728,27951428,142198937,94831903,70516439,1000000000,66582526,1000000000,134551559,401936111,3866428,466973056,17960026,1000000000,257166267,1000000000,8434563,151072951,36993147,257225392,38660149,1000000000,886126903,15503674,31954165,26443018,323357656,524326236,61542886,265741291,731399802,147426750,1000000000,1000000000,1000000000,310791921,40819486,27066484,329483483,1000000000,1000000000,66102789,310761599,31157009,6161242,57032986,10587858,56512108,196492436,44538444,505594113,97193666,751274403,106236069,1000000000,21053660,139596900,222469629,784508468,96703059,7023870,124827529,3797751,20238783,356935836,504840218,329687,16393007,244220267,93871205,171766142,10867439,75628274,214379081,1000000000,46349580,451385745,381211380,1000000000,80337758,19213400,310070825,103117611,32174042,93857765,197800279,260634171,94682149,1000000000,189685232,436142468,55365685,1000000000,61186952,59845695,1000000000,215295907,10099978,84675815,31959686,63589913,7371580,20360010,275148830,147068193,77587787,140039719,41264969,277376456,295689847,730196900,183874527,30554193,15450279,56869611,17644394,1000000000,376556146,278992791,13562349,171738115,1000000000,4932292,50595079,66050852,80938140,1000000000,175904750,1000000000,366753987,338178584,342294762,75473116,297481433,79795485,12297820,265982141,1000000000,442687559,16345344,215834781,144058161,80226653,239254856,259152259,236401304,115886978,130871589,844328647,440334036,137735617,1000000000,498502321,19323309,19584862,35398737,34007570,223221676,1000000000,137626743,1000000000,434569842,745550,16014441,105760246,984099681,388018351,17480181,42134941,4807323,97272333,841987818,230487714,38746785,181660011,34117855,102945161,306643030,489599507,1000000000,236826404,35385672,1425193,82372634,192063005,391950064,748335494,463013558,179451999,45292599,9848237,450195188,172925705,1000000000,474691261,495502489,283567650,2010711,517750849,201253075,40477628,245365070,275826606,45502688,164872459,873864156,67626183,294131582,742805471,20091722,459166086,22856713,47513449,163478178,1000000000,77569145,281897144,19523179,20717063,1000000000,525727269,41017025,706828416,348189512,189974014,250835777,1000000000,64289836,59048832,1572493,12612736,193388773,101807103,483047509,112490072,283105387,4772359,277829702,9673220,2699870,265601315,38048054,46416574,154239828,48020297,80240030,321081659,221539847,149412494,52682846,13030379,1000000000,164353526,97946712,14848243,152374557,168685091,1000000000,166546817,13963543,5360143,204328424,481834009,461134318,49073551,425253146,55164704,1000000000,134978380,475997098,403134502,83872842,1000000000,770145080,37503035,9133790,29974638,6458065,1000000000,142877193,436575951,107638559,138695476,160130015,6377684,92754924,159750963,151544733,39999173,1000000000,1048482,1000000000,49322121,141805816,21244854,25850159,99580311,372714327,604951008,322310729,144460288,90875333,105550977,180077487,1000000000,839026,218649955,20511411,31021183,684630955,19327182,39776360,177433351,13704002,408317015,959932492,61037202,569217819,365530507,1000000000,241331739,1000000000,244538685,204926715,1000000000,423186795,475771594,347613487,885854873,82142678,1000000000,84844148,297048342,435569425,484196204,301290880,242409852,275962060,169945482,46358907,384546922,228972833,90783946,706104466,199069415,6592327,538932642,201363494,1000000000,151608905,140173328,272595837,148628245,66384617,438813112,29103147,238908200,53892932,121656406,143564452,47854723,916381187,234662865,376613732,67265429,61406704,1000000000,923199346,28727843,26600990,678819927,436239418,536133258,175171221,1000000000,126655892,138518634,211841765,169306469,30319355,75532298,146407580,773234586,231943262,388762501,32762214,117666929,1000000000,153635726,3581937,600190752,1000000000,551988453,1000000000,1000000000,94125438,95269751,237039231,19409352,173009552,574606090,68243394,1000000000,2682278,375582867,794657255,1000000000,367406740,1000000000,6364037,282493082,619746785,151394523,41305119,364247234,314327879,247020087,124312712,362643455,106502480,174972029,1000000000,561276093,167780707,8481268,279159973,3059043,61454024,57451943,96368457,73531141,1000000000,116270323,363541048,122984627,113994113,159082354,266419055,389309983,918307403,525022959,115035654,1000000000,1932556,608065413,22146358,25764832,125654315,101984216,207761196,1000000000,25893352,679094427,105599929,969456771,347389918,217297615,905491023,124616766,26034337,72022822,10093639,100819440,346198218,395960108,204338364,134029705,650533523,129667809,1208084,276005684,167657168,196323724,1272076,36988920,473723380,233463,542539172,13568003,238873222,105462197,56257374,87978480,109836419,189550282,1000000000,35894385,398793164,59887682,336226052,1000000000,94787263,858385012,183566152,15958580,125564357,277824263,380919623,38629962,186787476,227914800,139971338,248659365,208879940,99834357,4690300,33051577,998951051,32062049,48322864,135653783,1000000000,367209182,504384457,29347673,43145663,11130813,66434596,110156127,52627112,38473391,348791008,40775170,617025291,45473212,148994752,508805360,485731406,93799414,1000000000,29323897,94432471,957488434,30368597,88562871,84405060,45023749,534946887,16122860,28318877,90511935,495396430,854588,1000000000,23360492,14986368,196171910,1000000000,405829220,122627201,139645308,145683458,244583822,63101000,289312512,279360874,346327546,176835193,15670405,182138171,298254622,1208132,227695891,150865660,141099183,114260188,201981368,6036562,224728241,69887509,195630811,1000000000,23141552,13157845,1000000000,1000000000,21625433,246764767,118265518,27910073,148388794,311247712,433995211,162998483,128516161,217023736,192278806,339504614,312916084,1000000000,16150106,122153014,38514708,133155645,113331355,241564568,557680,1000000000,422637040,315448648,199685438,14860051,64394059,251352778,574605371,214219513,73444526,1000000000,204831369,161646066,357137199,1000000000,549499013,38869909,17763091,33484318,380882791,301340228,376389618,57084289,326918796,190222954,1000000000,1000000000,47391972,54410921,184587716,64748176,280246634,10318558,247989341,320778360,1000000000,279432831,15701735,31952761,1000000000,811273716,157714295,88301610,145062996,407268052,473986317,90263802,114962027,100639582,40116785,75793162,362031079,126520037,151427480,4297526,597885230,54134574,1000000000,535745782,1000000000,19881750,1000000000,48827956,255531229,223211253,173007552,544405948,250213122,1000000000,1000000000,246597051,36893119,90558643,61672973,43919520,248995941,168251270,37268920,130419926,53634,67375373,57669526,147311236,1000000000,180063822,857050104,13916493,325841201,218774517,80790039,203949298,1000000000,563976,367353262,460348894,392031163,104987312,14501823,115339022,176569224,177711809,302065510,44912833,29550966,83152317,213128147,98198597,180951441,317557549,328349467,490851316,163889590,126053824,1000000000,230432897,398294948,1000000000,175226,553990400,5566788,47219526,77506612,1000000000,251984766,133439813,35913868,109078904,227682825,98763113,28300226,63708832,168076907,168901587,29666081,98034199,99773795,173445677,112333037,599928159,2469295,443910727,185037339,51247297,561641114,162226077,322891857,36035880,208773895,454308761,208072797,345804635,151266995,184762874,287683337,183626202,22455926,31832265,49635922,231730853,1000000000,129470933,1000000000,84662780,28656689,145244548,163314083,22283389,451842275,88097224,183349901,8452078,652744198,121034921,758734413,29330976,1000000000,398688078,155324239,1000000000,1000000000,54826256,156252943,5067173,111600973,130733246,165547293,559011370,87003657,317955610,404556154,194090821,655120196,73932753,285921358,390201811,184375237,443583969,258583171,110256862,455332706,203459085,789226,168180772,4536030,382895544,58965858,194594411,213815336,291404949,535138476,70473793,1000000000,77100767,180228708,76599382,84538739,328430126,760898692,338322727,58846538,679466023,141674003,188740603,160597022,331090835,192826383,41159510,1000000000,179826336,1000000000,26845362,253697860,83174837,763717776,123572127,215331985,62755071,444573919,39888202,605247706,58900698,67987149,61542401,133872740,34770849,1000000000,69925755,195813852,1000000000,472681392,264498831,48208984,307071156,380409689,381291336,1000000000,109177724,123773958,176705018,1000000000,1000000000,58899519,114899980,474551003,405839903,1000000000,147137171,302046157,546764,158200524,1000000000,64732336,203211757,136452248,941777,1000000000,198365994,61860812,11583029,133329525,295665774,74454162,115369550,1000000000,57703568,1000000000,2605224,12731754,1000000000,547395286,1371074,296545377,77440168,425410121,19271154,302942840,358150901,427191004,126557718,206033350,1000000000,121394871,59434772,203028632,157615945,322401810,42357146,356437338,310231690,311588817,87670812,494524385,39254593,403556635,18487173,28229950,378613379,177543,253218124,770294480,216950149,855734439,52500193,426778197,120557887,76992890,564297810,5722526,520475879,117179909,47642566,645594511,89353236,92160105,128416415,183527275,468463636,8118687,121843792,1000000000,218015133,45316096,1000000000,25312282,1000000000,1000000000,416695074,1239424,79895118,278791326,147283958,107608586,158203778,218246073,247683042,56343917,348516497,144511528,1000000000,101235759,97119992,169520059,326787531,370364426,153225733,8764951,197913582,7499857,148765238,39889116,30458253,1000000000,215117468,443427320,88457955,258212442,177831801,351869995,6504283,481321105,484404618,2154768,87199917,1000000000,494408301,1000000000,119934630,46059023,113066429,1000000000,652340005,208318721,173189219,428184671,508716766,7335820,401652765,80938152,42849431,1000000000,500272677,590759776,95641051,37592670,5755372,990102729,69090861,11267078,161365853,42761054,102779485,811062229,201778951,56828958,59135953,127569779,1000000000,562146824,54303336,392236584,8547905,74290757,1000000000,289452992,81816567,217132665,922454517,1215743,75427183,68951768,906746368,1000000000,344596655,1000000000,59244617,44899087,369607344,1000000000,28346506,111936852,31130013,735229211,422119415,20905554,28335192,219973810,39648584,229840770,362135,92841677,198165335,477112417,26285780,480527343,297497503,154073634,537018528,331610487,96423723,88064142,164620450,200473115,392360568,1000000000,447432918,9850613,110256407,157398861,26765633,258435260,731747612,1000000000,15249427,147121626,328184192,61760420,239980071,11083090,9682964,18895839,26640667,209974668,183079231,139605393,6169953,24111270,78197902,259628121,32326655,1000000000,14989754,180545277,846906938,360079799,35225297,257394905,510068859,203801191,80669638,147484210,615992577,19848678,143503809,22227301,245415490,15300157,13907424,124046657,117705052,28088597,1000000000,8991862,57705100,37657051,138482131,230818563,1000000000,21747585,305781226,35893058,262045040,307811376,106754278,253063515,247853625,8485405,1000000000,372489721,208529129,17593278,98107485,373479536,189942046,1000000000,201269001,24192113,116035478,255553544,306887043,25942242,389494892,368373025,640341930,187633985,463576087,52555080,370679448,54010539,229072834,5401114,1000000000,148024554,430015684,1000000000,458204951,445363453,125066860,74490496,433008441,157156324,236132690,97189710,27640356,160351204,1000000000,58327582,110225649,281389867,719429796,270703730,61082019,712072134,156274021,191323307,114859576,1000000000,707830831,260598611,1000000000,299920169,701711347,214063395,1000000000,21148092,105912073,668193913,495031605,152473604,280231842,197048505,73131681,695692769,132702793,344774123,4124287,77254991,4269056,470628520,23565272,396140470,15455455,755361250,10352686,164808569,219718709,260228681,184311362,27677986,82210168,129041393,1293937,7365418,219368992,152557404,1000000000,754101420,584627384,10367114,395612,175690582,232831667,435095411,276393916,14610637,60851048,90114387,254579630,358396511,199366186,228989359,63164041,244174160,298747382,1000000000,525477133,35089735,94057789,559912888,266001525,185804541,379547916,477907752,32374,100923279,133750497,31954479,162280397,953304763,339096039,658777783,250461304,121552997,492898983,19935742,135820552,43396537,49093162,9319462,440203577,68078202,304119417,1000000000,204947159,26501434,113948022,209145099,76143559,1000000000,2741049,103493633,89538884,58918086,1000000000,844668551,590398611,1000000000,47585352,543160971,1000000000,1000000000,3699164,1718729,118506519,547598419,419347186,532207337,492518347,1000000000,348600922,136730453,348033520,1000000000,1000000000,838064039,1000000000,1000000000,778848006,20992382,1000000000,313131139,1461639,194007174,242815969,192331236,222002106,1000000000,707512900,232797967,89271304,30265563,24473596,310823796,106943164,177700857,331763425,406725650,55946240,16409718,1000000000,330209856,29711453,220676614,1000000000,102317847,84254342,594103319,33025434,448491290,164612234,14082293,1327381,1000000000,561328667,50065361,1000000000,3947352,164451392,320885532,1000000000,257987494,233577978,26447927,4740307,297734,71447407,730729472,300615562,289189137,185241300,38675672,12449723,1000000000,50915174,178782489,1000000000,39724444,211700099,71707217,1000000000,169059725,50664396,68264332,215898870,1000000000,22224831,76159750,44867271,272681407,1000000000,833903151,663341482,161056812,4515630,200700739,151543702,236235903,392341719,125963907,166645278,711985335,268359429,112405594,22343918,87028300,241093567,37642212,1000000000,85519483,396411111,147849849,111867458,36134302,129573364,215965694,46818219,239129400,70869456,9348750,129083998,0,1000000000,86999270,25173238,204531882,1000000000,267000619,223623778,3441562,1159589,4633827,501528498,1000000000,96095291,1000000000,100994040,256320480,1000000000,4229734,208083536,31412639,9523218,2066479,739856989,443657341,5896636,163706833,182308435,201110313,38706455,87966387,21081160,392546851,917755988,1000000000,1000000000,317419959,18728494,1000000000,8738310,1000000000,229165917,229434996,25100792,103781142,254907049,63029086,1000000000,11656199,380828726,676288953,263777288,156561729,12157757,46282316,21373333,42420855,1000000000,446769106,68238083,511186426,269362592,821855831,348331803,73459715,18028647,146146268,997849,916033378,168434868,1000000000,280877499,385819337,67488259,164968584,8572560,1000000000,525505357,123904621,6561877,439809103,1000000000,205832699,195142352,258958993,258686481,46078890,714228362,234698596,2397339,34890864,354710557,28249225,21447912,553215125,37586660,16701772,227266508,123460167,37885670,415894980,599113092,1000000000,54481990,305364930,969649655,46549583,270079670,80712732,11169458,64371213,141657705,82145271,191194344,8377470,364433972,543439244,5849964,42463963,406201156,27085474,96980109,13886584,344778248,461743503,4760746,130212615,234188987,66186388,106147838,190903167,1000000000,1000000000,335229697,389262102,25263506,765998877,28026115,60733109,2755322,191580902,53880793,11028242,1000000000,374955555,90973266,1000000000,45207460,17342380,197228777,108360827,15269887,8559753,2579694,1000000000,204760785,215714043,913061235,75008407,129158388,73209457,325934844,74951059,841761584,111635812,194762967,301971018,607644982,18075864,1000000000,414341485,225246660,225710390,191862640,21375875,14480084,58082498,1209803,202407990,258422357,143709723,13829108,19174949,338482220,1000000000,1000000000,331960764,177803447,41150678,298720239,340360759,477441352,768912938,57054084,750695195,219891721,932089305,176868795,705822,44850932,23272223,113468507,863835861,75159573,394838298,340915171,202235486,959595369,706612906,230260754,1000000000,179597925,115695659,229922128,476676314,1058243,402545965,2167973,62166573,439260813,50636234,150404924,142617049,249053,343866716,311611726,60220169,595808,213823355,7441825,195726254,94523247,720843764,9239869,27920800,1000000000,89609105,434399834,271219094,175469218,353660032,88749053,279383362,68287716,1174527,44894128,121362807,258651923,233605893,69250182,510698250,185855956,396377902,559428412,124955123,51974518,221301748,135334138,454705731,185248317,125920605,956589974,226952055,252202272,1000000000,269357667,49980637,673758060,1000000000,202691023,1000000000,1000000000,84103919,1000000000,723712376,181083953,7546624,1000000000,520139688,110402452,607771797,82785889,286787910,354354667,417578467,233635357,355862948,10625381,805234845,89748406,1000000000,5259189,8466854,1000000000,37108371,194159714,225440375,86299393,529213296,219633468,1000000000,199807913,204789140,71313297,62920872,63564990,1000000000,1000000000,149858024,448969915,467909232,72091664,201650443,2271565,9723956,124981206,33956500,3086562,215790104,76616061,239625622,150478513,554078226,105313315,1000000000,42874939,251363722,66465879,5311989,12807535,9607627,298211355,58657463,124002974,50063863,1000000000,39469605,262376074,301785686,1000000000,6848101,862090731,66175426,1000000000,43661908,161963680,88978386,1000000000,32970350,611879395,160301788,283412450,271308367,35691624,16101483,365641175,761879806,334864815,160290904,82052132,1000000000,235740743,109082075,60503124,46710674,201109749,297715148,35949071,6383893,10466005,553837751,369098081,12022016,147575928,1000000000,76005710,224271879,232608209,167082386,146781149,1000000000,158528592,248672045,1000000000,90649635,133743678,296196217,82547771,45732365,73533258,856756747,3552020,296423026,50219143,1000000000,84926630,388535129,121427790,52970164,97708580,30662311,281631697,134809277,37180921,354034935,40752393,47956504,245313149,172433675,22666464,605816469,44757584,957669278,1000000000,16730364,276707964,1000000000,12407014,14381850,42403438,196593147,146790714,61817654,21901557,973930,508238567,614468691,247026538,40657235,14825910,50926289,4017604,379603446,805050802,707982266,56051268,26854007,1000000000,85300252,49075826,206492894,79535651,30421392,66356330,1000000000,785614076,94826815,1000000000,461664419,6595579,107542256,96708968,353755907,479906955,275458810,682911768,337898890,88803598,5705944,376540644,133820497,21992600,358772375,181145418,1000000000,27071319,8152854,7249539,440520181,26791876,24801177,275158854,1000000000,301652823,471558118,644129524,507935226,423889106,102522764,68502164,9657488,307739904,1000000000,413878545,5510175,164379269,195743245,39322693,197081505,122169188,147894840,147649656,176036191,37554020,416772608,83842245,49292067,327143089,63221836,372636588,146698640,4041506,794040710,147305026,4880761,330368680,172305948,611457579,632509631,162932244,20189563,1000000000,260027851,70224726,144540778,32510053,935101,169265519,107950469,912475653,26772258,193305736,399558919,1000000000,203333763,44811433,411176899,1000000000,73571781,25152155,122309864,952722327,49345681,72267575,90480425,31089168,133917745,432814132,86962477,137277762,304291416,1000000000,53731879,200952781,739103367,71018630,23154671,277448515,55341486,45878635,38989901,68383841,59010512,537721108,38393779,362871211,46249312,205919512,1000000000,142673427,70580825,4976947,11352592,111196092,249372320,158976105,303460560,71060388,37712531,1424558,33933127,100030328,77860625,243934839,44810755,46300832,123859719,45905897,165754614,487139316,416134059,151773141,439720,150164348,1000000000,134061890,88849805,39413236,1000000000,203467399,188610422,1000000000,115756048,684213318,758861446,253082113,170753306,1000000000,1000000000,57811438,786916262,72448821,307822948,1000000000,42230978,1403213,217052044,146757637,1000000000,33837531,4836476,103963684,6182354,470970170,29344028,65458111,1000000000,1000000000,77885570,9596582,2128322,241572788,276154866,276053132,429561193,216951062,64890389,1139701,270203437,504783395,175009508,63416096,96798809,507507129,1000000000,484244951,1000000000,1000000000,205076386,76295886,106436713,836000113,39415494,408992212,711244081,576138828,337749145,19819066,111860777,277209150,79053427,45634555,104680035,59439788,240019128,179129114,69292228,59899250,406926097,15460757,1000000000,260843082,152529949,665742337,17367389,890333012,139071722,78244403,33334710,260296325,291894568,27232665,80536529,112673756,56624,541860705,1000000000,403394762,9856289,130123363,30430039,107139910,472054384,86819807,21309047,136751399,1000000000,104019515,256328631,209914131,72789481,138489932,483113886,14457273,33026566,164791840,66644224,122173171,474046281,19014309,89134545,673448496,74469008,2721096,27391829,145862944,242057800,1000000000,183022824,1000000000,859303092,922422332,152632685,1000000000,585550251,1721879,541786747,266690925,34414792,17229441,180115606,43042792,7586099,207471753,1000000000,410648967,1025502,6328796,170550811,122721096,1000000000,55339408,112672660,65196026,48783824,1567010,92328716,287206916,111324533,898518194,140538697,46266947,1000000000,16761863,285357864,1000000000,181085784,500976800,14323626,827063370,445062017,334934224,83879067,120193515,297067824,1000000000,22610511,206507502,620286941,56631334,244086424,113784439,320065803,1000000000,113353172,508169011,277029592,20292903,350094810,3648326,36982845,8893896,112465743,73868841,57044441,81066444,467084713,684699605,27156937,63701542,1000000000,337714780,211855472,1000000000,324128783,412191125,1000000000,189474755,3884873,159469191,504317604,14343154,17079776,869895843,192966611,47313935,63278589,4009865,269558155,104584941,73977675,28841898,182629077,352835827,410170624,1000000000,481353607,51334733,123367584,84264265,1000000000,116108765,820375287,167514954,238561236,21499100,343316616,7490405,199844828,361067611,56802013,202890745,417848857,372879748,305480363,37360940,232466707,112245430,123223462,401493405,338691387,7286211,127080130,16960793,1000000000,274794089,1000000000,1000000000,206327648,555384991,1000000000,105393347,57740413,676720175,23673051,112047396,1000000000,1000000000,78324825,1000000000,158095572,1000000000,83384034,592214824,1000000000,155957701,99128481,14135950,161885117,1000000000,756271549,12597531,70750417,407716969,100740047,357072795,1000000000,1000000000,173473405,8632634,106194643,34212134,25913975,46286264,7377218,579382414,190957341,150767950,436517128,406217818,630116566,412960038,178883254,197602268,97695139,244436372,5104317,1000000000,116782627,184190123,52725579,170029718,10775720,6994746,274670070,102450724,61272718,152191853,1000000000,97220839,19323143,1000000000,46168423,32985792,447765999,133386160,147296378,100312821,71326444,284512642,108052668,169403480,656574427,1000000000,3180777,126977114,26641450,4637964,186646439,34909963,108508903,154666316,146666635,102486619,18320093,96084820,327008654,551231420,58437383,1000000000,6728872,5591828,146228883,488523855,1239025,385025869,765367474,2375338,1000000000,19771200,26353714,15348024,673471111,891415926,66189379,268689230,77736828,121500885,19251326,307145871,235783383,7563686,276164,52599563,407926658,241969724,138418552,304633969,85377654,14966796,511394244,568056933,1000000000,1000000000,53020138,232287332,181426459,194241805,296630725,101227820,40434455,90059484,1000000000,26775746,12226018,473625829,742785797,1000000000,102257527,970242842,198510116,1000000000,437053345,18563098,87073267,34014167,44387695,601504387,21621601,768659216,1118168,201881911,1000000000,244507728,34953999,240500259,240198843,426716156,142574539,453562295,969350,12674221,380546611,198270200,103534939,351588508,31836750,299517973,46106872,147336231,113450379,15643540,1000000000,294766524,45326313,242416770,5660134,320836579,305548649,621090612,337810155,55201300,30783711,54007294,1000000000,643848171,378973250,82443499,347047988,1000000000,31103397,117845163,130763733,191186652,324560143,95159442,52147287,86662364,449471290,441719046,1000000000,86919633,1000000000,458839731,58599490,228485850,161173319,189769057,15076956,224919057,801960,8623248,16518022,13193969,214853139,86364883,39436739,523482,671347686,20927543,220022216,80948872,33749731,2311424,382354703,257899384,140325036,18031524,40336118,342591645,88992876,1000000000,509955516,190092083,58906025,287979487,114358012,160560644,341151021,205597412,53069043,929349337,40002216,15473829,80140942,113450212,357642121,1000000000,93016105,1000000000,129302341,110645347,307871383,40001093,64619454,560680705,432827550,18125273,503082131,207906600,80366602,67430823,36475035,490714658,90965264,159812826,311430956,153087049,1000000000,1000000000,776779441,79626837,542853685,702876,309542745,173838859,82356367,19300890,18820588,54248450,54045103,51110518,416700739,416845671,625487135,11812621,40355310,365354743,231871322,793213231,1000000000,109452796,135694788,2769540,388248893,1000000000,86551372,104050111,284000050,392801357,35547066,175751582,1000000000,130971624,2679593,503776813,8141271,325217605,14477043,92679275,1000000000,106516519,102527337,1000000000,1000000000,503834234,128601669,255773617,487860765,1000000000,42684661,4146994,40734668,66159697,22891851,206531870,233999744,50933483,646980905,127089959,43903900,868196442,880571358,33041760,312553823,319753102,1000000000,33888148,33510944,292825927,447420637,31087180,1000000000,500300626,103986903,71261710,1000000000,1000000000,3295722,411319689,65575180,366053536,903810210,995086246,26054812,13486398,88855644,264645500,38021385,86455875,111169000,322005704,112742708,15917690,190611809,276973185,378172216,294144000,155915777,536802554,93454812,168583960,55759504,32184856,173386152,223191638,12570033,363984917,199504494,12273061,72695522,216382630,121850852,100433374,512582104,32627597,295711118,215872995,396267455,99513030,79140441,1000000000,8409812,405376930,84306704,115363160,1000000000,97512865,481959155,490900306,344704397,958181967,306399095,109950491,1000000000,366200724,49084217,143388824,139610313,1000000000,244589361,22728871,82042314,1000000000,117347684,386385447,50868226,223358772,13854672,800031050,551008,29685643,107275964,1000000000,597038645,216862221,33208596,1000000000,12486342,190944036,1000000000,54547111,1000000000,161083394,7279084,208418105,248978081,66903674,65629691,1000000000,1000000000,128964058,12474085,1000000000,323130314,2551883,642967805,480199164,563124629,495063405,160928294,178926104,315361536,312623832,148882486,19047617,221048277,148288849,10369302,299565152,181847259,58676665,102866091,430012808,695954923,1000000000,74796454,59711699,57823042,190932132,218221102,8346463,117799107,231456403,69454262,287667244,55290735,23262587,1000000000,112372566,201389016,475852212,22356127,66478900,184513354,314744816,10262493,142155183,303287355,344405611,376087767,31281216,420601402,221387912,291379469,187319153,1000000000,64339018,17424431,437322482,176581761,223082618,1000000000,235721629,168366016,55790027,181967935,191128444,491002080,26255601,374497447,666252505,647331003,66214712,258530607,3887883,65951197,19365097,43023803,285812502,160789747,341678005,119196925,371969981,18389008,331411975,657828743,91301717,546870945,1000000000,74575285,26908577,110365107,45346765,59170942,3458210,26612682,775077727,453462667,17925824,827516,58481334,138922434,338771407,1000000000,4721876,62958317,172712175,145383277,233238905,1000000000,974054260,410945593,43020745,328819255,884227062,200864528,335335667,362121665,59705102,200738688,195035530,699940154,160368989,296592345,181946622,424867242,24659905,152904433,62138495,144217314,459103144,158257451,469877091,327027016,78279128,1000000000,761502729,697865051,19726219,183548,228106927,16830036,136712749,43557674,19684249,95798024,256168249,295843044,371130404,84352074,123549084,173774713,226980440,207106763,93781297,25652140,129309798,202878814,10543163,52524597,165491457,145100432,855808803,197687835,1000000000,251091672,97342350,531461793,97057809,153610957,63847412,204529014,22492526,151544980,53006385,56811700,91187232,95974583,734971035,18757144,342715935,278803251,59237177,417163047,202223048,384027127,37573309,1000000000,84356298,745513269,1000000000,497746012,59315721,27397217,1000000000,129960713,242077457,1000000000,54159627,393754690,211012335,26374056,116716776,704707716,108221125,1000000000,478656199,684739479,233583073,1490162,331998097,672875087,399296622,11161712,43832146,386420969,556148926,30564411,356087969,909912748,340509419,485877221,265692620,1000000000,394679472,21055171,81014376,50018092,56387713,1000000000,122695591,201709898,232946140,289658338,13920749,297556390,77823921,564682855,96525352,306155614,578432270,599778506,383760849,285678323,297204448,363215647,6070970,1000000000,3960074,4244419,66217823,250283427,209360228,28106999,147152537,177119971,78245896,614529636,222153617,170787289,452074150,17741002,113414033,99278869,869672318,119204973,99606311,177363288,341814824,222800002,684917919,366744528,747743161,84598837,407029768,861152,5560470,67288673,394590459,135514304,217523456,76276908,172031998,1000000000,224022403,71850771,255804257,3770824,250922974,11020284,296925657,168514570,988411273,110575041,17434347,1000000000,1445356,257793252,111157398,134230537,51186771,234857077,1000000000,12304794,42095671,57629609,46961643,540241664,62142252,1000000000,43249992,97822781,30837227,580280540,438268422,181361177,37039616,88616968,158412689,74314748,7034612,268101612,245319575,56967587,1000000000,33121417,4676850,139044554,4861928,7906938,255177646,1000000000,20800671,347865814,395792226,1000000000,662659532,85959109,57689225,1000000000,470517134,389169424,82666795,1000000000,8302768,209272198,1000000000,4860417,190812358,22238426,1000000000,4533395,756591037,138545228,72256239,21145998,57971779,41707225,303912284,178870984,2957214,3666296,589954394,389231941,1000000000,295544622,305442113,699440282,146799752,25369556,145288545,3723716,294051016,158628841,59187569,58066230,1000000000,88597380,251684046,9131081,676545939,55066448,73686945,151421362,166809079,20901198,7920854,31177747,78876303,2094591,1000000000,543466133,69379264,72418639,220353109,80818548,1000000000,645490977,2455617,224345589,41851929,137414656,6573904,156983542,263299182,397778317,602083416,177643374,443194895,5815281,196701841,1000000000,61346786,24571568,34545321,115855106,535170722,135987240,1000000000,88438240,28902370,18859408,16038059,44917214,41584788,57187260,937472126,910391477,10258613,43570499,10403466,431709149,271002315,179096202,1000000000,212619334,231443524,207476173,14505547,51275528,81050087,98435893,67381093,345923776,3199005,102575809,101778619,132655862,32427788,174259212,1000000000,1000000000,4522947,8819893,177301046,131669298,82480814,4130150,6548534,58053975,31276276,744845823,191428041,1000000000,50251562,1000000000,709263572,69341888,1000000000,326896539,663206175,113979477,42184731,1000000000,46473113,107522952,288573756,210750934,112041365,245416117,46052651,365176766,1000000000,47795770,63749355,1000000000,176480646,23172577,241370121,67070894,41573984,121783939,337144301,1000000000,129069520,164925090,449247090,7076063,70659060,483471236,370623864,1000000000,76256730,170490621,256572628,134370665,227894610,57010955,270445204,977264546,258136342,1000000000,197529509,269184669,53252937,87757425,37581055,80909239,147418182,1000000000,57463510,40248934,241872256,1000000000,41766542,194137150,1634194,442189052,25693789,350016106,458635656,1000000000,20332016,963037375,350996005,59690958,29426306,422432228,1000000000,192426216,66591877,27174992,106154618,29524056,192054464,50379537,227512439,203495880,479367788,129819724,275540852,16037585,1000000000,219035970,206950200,174201201,234502636,1000000000,388697347,59222283,144303035,379775447,401384916,5880575,523485007,35516252,386981230,214695797,4984321,1844473,307205430,9324133,794028806,326946786,1000000000,464929852,210060511,369353887,80698720,464260544,2734456,189421805,23906922,55006341,176465963,124507160,125976319,102754200,111092333,32281571,97025280,5274216,406874364,156105388,100673037,281383295,1000000000,259495017,48649004,490793468,172694425,400519502,273291884,228151184,1000000000,1000000000,154171097,5870215,191605797,5768747,3729018,17853935,19156977,38697738,228030417,585989001,17599288,189167677,230178173,127296040,131878,46423742,253176097,13047453,1000000000,227557851,203447049,535158481,70965088,5561456,7783793,172373328,151043103,1000000000,220812917,95606732,13920085,106178010,402194764,149680923,96882699,159334170,1000000000,309478968,215092826,367323174,558812862,41409340,8090241,232572291,79085208,111342426,336956634,1000000000,19215067,766582791,1000000000,192684405,87361189,5163235,940695521,346524452,228907204,731959305,1984003,300209984,74104835,23030265,1000000000,136316462,161688323,10303732,1000000000,81568868,29635182,345719914,61781968,1000000000,225229164,3043216,712640987,11107434,92106205,315555589,132115175,373193815,79217377,173514139,109254700,272787761,30740051,25106070,15505117,1000000000,367124857,13121801,1000000000,1000000000,11703869,1910489,66776482,123831020,34778746,1000000000,261417085,63488590,190495492,25496897,233349690,87431110,713841146,1000000000,219859085,1000000000,52187243,1000000000,104793721,224918628,1000000000,4041125,346956751,352964941,28617342,6511692,199055281,64784524,73963194,319608522,1000000000,634233581,1000000000,281668239,35351413,1000000000,6573218,62977928,1000000000,1000000000,282496622,400967805,25686282,513035875,152929558,101660665,70124033,3040990,9239462,96808592,168741312,167918958,156546369,79519363,111324112,81658119,1000000000,318551814,100388555,151674433,34874095,137495333,232456415,506335476,489007674,232217669,91436769,388719905,103611183,2738609,52451359,329817863,514401971,19697092,18060618,503865589,81005806,456251297,52980072,36350758,953926487,211692866,289442792,366166003,278754457,58925575,26528253,330508325,155485047,453752874,1000000000,21595621,218663377,27788153,1000000000,58602697,221751037,555053977,32474359,318428195,423970562,65810439,1000000000,33498568,1000000000,249874716,113442391,473933797,1000000000,202858264,272041970,42908521,1000000000,3253309,166772441,113323668,21092178,275288681,355121378,1000000000,257566357,37877645,8216568,553787224,457045921,87912602,463413566,228908351,106997603,70274259,173050734,1000000000,200214871,757348,68693875,1000000000,894538193,216973062,285689996,29885184,58539331,57137603,130839494,820988631,192077245,121813415,22524737,342418226,429766808,78135108,162496138,219405037,18611462,152961841,176846649,1000000000,76632246,547518092,81057553,66026157,209818653,53645509,1000000000,243064170,6664503,379104633,6818324,918071008,26614104,58650171,70857754,114873126,1000000000,1260007,94824890,1000000000,10305422,256379965,385985981,152701313,149261772,1000000000,1000000000,474385471,147963046,346539359,325313,89895797,6136506,114736488,56186890,90242035,19417871,38452194,399213104,65378918,1000000000,69336623,311045945,290701,26118681,541606851,218819252,599515130,540114122,9962143,53334866,149722328,142352358,63861583,115801925,72089509,1000000000,428465769,485878306,121484596,29757809,7008423,248149044,824451340,11331285,98497701,1000000000,393575551,142578540,177863880,412227165,23047402,112466471,11416048,61178057,187890307,128297080,55926453,1000000000,66237733,283783619,9799562,33281832,192756512,149764379,443673585,15215361,117270207,393951667,1000000000,39245777,402855141,456131763,55840168,27674867,295344374,69364524,259279410,22053710,92957623,217850499,44980304,43532847,215088653,213961107,16783418,165037944,156099160,1000000000,5909154,950331791,365110602,295252011,237676240,60141141,678094,9020979,41290163,417712970,915800267,32042951,667689462,225121269,139320180,15098756,208806818,277614610,1000000000,475587127,205190939,206492371,910682715,460173,39728826,590625463,67416401,478809761,119308991,256288903,36127855,499266886,174032029,173051108,100443085,103272778,53864040,33141728,97277145,267357499,88212637,521051427,324110707,184614728,493539862,307277564,1000000000,42237922,271521161,66898572,306828487,319049135,91085958,363293540,523980347,418051562,573454506,656900533,15726043,1000000000,175483782,1000000000,34228160,62884932,36280114,264078253,203517510,1000000000,449168733,1000000000,1000000000,104866523,43816707,985980693,10881594,305050953,1000000000,237737195,36094311,351144921,238669618,339277106,1000000000,785251129,1000000000,686197585,109576133,184204979,437097067,715720819,35622549,1000000000,1000000000,146139728,4084668,93657064,245593814,45795025,48202448,174409316,316092817,846424,232694266,50973156,355871716,1000000000,1000000000,14825195,75511608,1914745,95026843,1000000000,1000000000,6764710,7831193,63482700,34845144,124687059,276941450,4197556,138401689,13559502,299939680,334170504,270592974,33325690,570425266,161242604,270282253,116074774,159649172,29129005,19549802,560913230,105318049,80115409,242047147,141939535,130108811,62103379,362050109,1000000000,123548244,1000000000,1000000000,157041782,85998580,191722279,220746413,96759257,6374290,526121634,14733408,248973407,56551112,213900831,712601955,1000000000,164459558,76490977,518159,12432165,250660865,12856228,151280432,39375200,80002114,32642155,6831783,11323094,47625444,388845126,1000000000,6853760,887973216,19569966,237285395,255398067,311078857,43681782,100283064,546335322,33763601,1000000000,11150944,7493277,62344579,126844697,47019034,292716070,139248261,310159363,199766152,97188812,674916373,30199991,21297356,172899379,169296090,1000000000,897022132,64631389,121531328,217870194,98196994,432846532,327679339,390755185,227688703,16039683,98638951,69308459,144342465,835760600,445641233,215719685,135858829,129819673,317743782,124756839,402523435,271477962,312345808,97298701,209505679,66410216,146531924,8182194,260648052,1000000000,1000000000,483847564,353481489,216818951,284625777,45361677,10378719,343208769,397450268,121492217,473571753,1000000000,1000000000,252038100,1000000000,1000000000,82846891,1000000000,158513471,478199886,35532933,470489096,27093194,840703980,846064937,747333287,133803158,929865917,215496884,2114730,380574146,381702890,411132837,22818745,270353238,45612913,29622238,168392417,61938771,1643551,1000000000,29246740,411254266,135176640,582445507,196619595,350806410,6660394,769898293,409364774,20713711,754876029,4557535,245622760,270591999,120731616,1000000000,984568,50060635,1000000000,43804331,226799325,38044435,350176379,5054226,80070416,55163385,72371185,83590495,248792764,774465125,1000000000,91976503,345376971,54013,156176988,35798401,215014528,439487190,70573430,265804,94109728,372262704,342964518,132687027,263979096,337512117,152608465,181685762,332466627,1000000000,217915647,64511222,1000000000,379977209,824699662,133226092,79275437,4664699,92649427,56209958,1000000000,259500848,455793816,797989862,342115365,133033234,500157649,301113091,176747703,101964072,206093956,96570936,1000000000,320689899,136473290,9615847,79598498,1000000000,94654970,1000000000,108890559,384610266,1000000000,66868147,33106066,69351803,72238690,103407044,214346506,183437095,279252126,16130694,72306197,201806748,672126885,65717629,284461147,291465099,45594404,977746305,90553597,79898605,6953235,1000000000,129264647,90015148,44230078,1202734,14284764,1000000000,34626964,2685313,97599484,48502172,42998683,53182778,127380343,120395295,186678142,75097635,189139468,742328722,25038040,1000000000,139163264,22982784,242949258,109612583,3441882,124338153,199973694,138764107,134783831,1000000000,250229578,280979434,114885498,74643583,1000000000,1000000000,329434483,1000000000,483917146,180730737,814115320,856048543,36181484,120580467,218058998,243658396,676936219,224000372,34953408,43277796,126436994,1000000000,408527013,156269800,253685624,73636247,1000000000,111757221,787828258,144310168,342307942,647060785,49074036,109136328,217113775,1000000000,1000000000,4511213,37907941,429526846,11157617,71977579,183131515,123900920,75855438,130174801,304382094,321738884,38909234,33192542,1000000000,107160245,7833133,421880059,381807233,739026594,307407751,316383320,84787742,216195663,1000000000,557490247,43399934,680111175,4327303,1000000000,447923844,45550534,680420,790350865,257422744,345140373,701911598,268889511,136810940,136631004,334875364,77764570,157867552,7622462,57897916,902186874,1000000000,134887540,1000000000,131582513,121333697,367412531,92393461,1000000000,11816155,63312276,59310639,1211225,410052443,163791787,517267170,75027034,283237274,586035362,244092084,196431970,93047686,2595118,1000000000,16006505,98041852,200711512,409392375,150354975,251451368,18591284,10996077,518207541,88824228,61411032,986553380,897411400,385291269,528972891,53059898,243049558,640384230,39080431,205994459,190497950,118458358,9477830,74055137,1000000000,195352381,101051576,318819966,184718240,187513695,391642208,60687100,56524144,1000000000,32108921,26877703,1000000000,343376704,70527313,31616715,6031781,329694745,398248140,74388622,702055033,62218954,15479268,429848456,234149663,811019176,688332273,47676492,14054015,564562606,147820262,322201161,411040495,103921570,114959405,1000000000,3466061,69674596,1000000000,1000000000,1574637,96829074,147074822,131294951,366251217,150996707,285468620,188569918,1000000000,77998388,6608639,55766993,168032112,103049195,1000000000,1000000000,277219323,124439871,105442981,74625769,114655685,1000000000,178850491,275443260,2890088,16407095,1000000000,388802144,587979747,952049,576402522,56258481,126823564,737163525,304056321,777897499,1000000000,45995091,87444093,460274886,436292375,255317975,287529638,212355120,79004006,198296280,117181092,1000000000,479371,387374818,105611055,183686275,160463391,399030466,105065066,58698819,762639424,5839515,103890876,187508059,54505863,159978785,1000000000,1000000000,49071823,91054992,262201325,167914855,274653597,8435108,454619533,57507916,31743946,418621147,140551298,55761932,0,42053271,115607561,45628581,56502790,6400181,477726664,159138129,157793591,101420258,121579789,203658764,25461802,1359874,487709470,1000000000,437579400,1000000000,1000000000,237756337,309125473,404737356,12631091,42091253,105025885,75060130,535888443,505821498,322351790,1000000000,61549114,486165525,356162,199521525,364265185,45275222,128563592,112458855,302740159,83253539,415515102,467816239,1000000000,307909990,150916388,110135761,157768635,305342460,416263925,75931983,38516465,42969967,358134186,87994520,101849894,230735355,12534607,107761310,42981608,27964673,247410403,191832590,352856598,5370938,586370521,155247836,225577205,341259957,203421984,739657035,46991226,1000000000,160418150,524816231,437112849,143361995,706667802,504220607,884754560,70550534,57351161,164527315,11543730,338584054,100361755,340891870,698793894,487984744,313409520,1000000000,8645495,21115545,1066419,4418956,56838179,4241047,112202967,820312701,581588869,676780434,164617033,155621579,16273122,190666135,54970593,354455438,261994658,257439195,143095303,11351758,22789821,69276495,91968918,235719460,41401525,228537019,1000000000,10672431,141511563,269002582,436789534,189879027,292173896,62931919,173297832,105060576,144613671,62433846,119659560,59561960,354628662,74791565,557448712,1000000000,1000000000,366596089,59415533,1000000000,190966241,66200204,951171432,117840350,620345587,25414133,179113057,41106489,36241335,234838343,116266462,1000000000,140509430,60339057,23674441,595636,205506612,59724901,423885602,1120301,1000000000,7910560,231967728,764043506,31100242,131792699,676939951,157253639,162540998,120663212,1000000000,105936108,1000000000,672556089,731756576,200932821,19036157,1000000000,470484943,55730932,560953464,203545062,56025668,60768281,34195409,66141900,792416177,80045740,175629449,72166948,1000000000,88137583,77926836,52241256,1000000000,422212247,3855496,1000000000,125373,7092045,261029768,70800806,267552246,187970527,34362371,1000000000,136837613,17541358,163378039,1000000000,94511379,1000000000,1000000000,394336815,401013608,76404254,565907,151598270,272225759,532073117,139399020,1000000000,81425989,1000000000,1000000000,202354844,52967590,380297229,104959416,21639251,258316439,150924276,95572158,1000000000,72466570,48926316,27275593,762912010,384301582,117464102,71868646,45582637,26134356,446614973,405459036,1000000000,90914408,153218150,639383522,190275093,2736110,971918552,280011316,44320668,65798522,1000000000,1000000000,92438946,125613522,1000000000,88915173,24206276,329031987,339721,187391981,750881717,487461011,49466246,82924825,1735524,68659786,104918005,53944633,25875575,88105392,131520611,861656622,1000000000,148659427,262449097,177414591,469948456,488949849,165852384,974225601,121200112,360752917,10013698,156228321,1000000000,258931186,515988352,1000000000,668134088,194931198,657045372,85048760,433485851,296352722,1000000000,115678337,1000000000,234950206,57698247,62998538,89953146,25051872,401824735,48225345,99197451,595507086,152467605,206751607,4269311,158067871,1000000000,366156426,110124468,34007202,1000000000,457573616,144716402,20494270,104632107,1000000000,191110893,14419772,1154297,879870840,1000000000,189418075,376107450,259647785,329044350,381034671,142835579,71176799,477334388,7789019,1000000000,1488990,199342745,171582477,57225509,77279951,297574553,258370827,446283198,123776234,89372080,31142828,33684206,307562147,257792733,10902505,259965153,1000000000,124705378,197367899,132496430,545404250,369425206,228083652,383780554,163545727,9938208,533245564,21423818,235908676,38758076,124249089,152940341,1569464,263888974,26565896,103792175,479954463,37698371,922117079,102466425,438538076,196027629,145003160,556934233,26853585,991640734,449229040,139718299,120826469,1000000000,135422605,56366757,1742614,19500077,69436167,376679373,197304629,1000000000,377790705,140542747,134091315,264062190,53713289,182301321,205604355,1000000000,1000000000,140052779,303488926,23862924,220166777,15381441,550081497,76725338,51146519,32419616,32722182,93898934,193230106,114707790,75157806,1000000000,283830655,194397132,10241525,173002204,588752269,258365854,128939304,202137570,1000000000,119209084,4064100,455517258,281090738,11673072,311138809,59185567,49127749,66441471,204173009,72211741,204159820,172055904,20001039,122485698,680594059,93258088,90615849,105620821,11687278,1000000000,391189572,669056003,254989748,200744246,546688369,50944527,282106,304433289,49686928,15527240,244950879,631387340,213251233,359922283,107869354,57606286,19438883,312042961,481223082,1000000000,52073021,2171308,360056082,818269468,80548259,543108552,1000000000,115077693,1000000000,406242837,542961588,180778386,187284023,175793728,1000000000,1000000000,24179957,317057221,1000000000,13957729,15691964,33977995,128606012,452064505,279743122,2038002,349786524,1000000000,929739361,1000000000,164214284,855367684,107636294,296322810,259827109,229270382,126508364,279051458,231688172,226055403,215452665,314964388,10610036,146998534,1000000000,1000000000,71986630,75471770,143054915,5471540,99211455,741259462,42944838,28269677,50035291,884274436,498148793,726088732,79227651,282512637,49279925,1000000000,13225315,332051923,43218597,6311143,626830059,113102229,406685540,401945351,40452735,18423350,39313583,397724758,218771777,434124607,430879448,124099181,547943744,952957995,1000000000,83148436,156673479,429110366,500751472,274871427,33417932,266123849,200756948,8215530,74136039,113440961,29003143,19470246,16553096,25860260,42609695,121808860,235907905,60095047,1000000000,35239676,203907602,6762100,56639303,169418174,1000000000,218424293,76667277,1000000000,9060873,428485600,223089571,1000000000,990464744,140205230,319468691,372675626,169209855,125388767,366998394,291299993,1000000000,98257993,616367905,194612958,13579870,46419096,19744658,188931252,292691312,382043746,331294354,9589542,1204412,165249610,14396631,45274204,217115686,126858264,153178451,706427451,4724269,7882268,413526442,292744121,222345680,255425223,339493790,128006533,53717697,52549811,28561572,228178565,65086303,107338996,996004621,731868,125927972,978795790,305840737,1884912,289509175,24649664,157384100,29342397,150602124,118962496,346101302,45707209,110814018,38223345,191167440,103980245,395630889,251763080,9518188,16613837,314493257,45348891,994338759,203898515,851501101,33743004,328205521,154192038,196156074,12927014,177310000,1000000000,250888147,166168562,162803867,1000000000,9352705,362383382,545478222,62426094,44490066,92486654,1000000000,23075770,236811739,503510387,97468308,38017133,13084322,1000000000,232567835,1000000000,61561669,202600478,348402537,115170027,78309884,265350578,278458986,1000000000,167674875,639300254,137050505,119298861,35491303,88540674,326513033,167149199,10317860,188755112,71828295,149387500,442936150,74769341,333705,224279047,98430460,187187144,59725951,1000000000,188035503,560505965,350888760,168069903,202634095,385791395,137778866,489182158,171208393,504971208,560932935,68320795,255677460,609014242,84909784,116884331,8544143,44105600,297928247,68804558,119045768,203764904,167496413,189848487,350607731,109789751,182086794,200802151,86744970,79400507,253564704,245443262,13209652,146475562,10233715,98024093,336261648,72406664,53258201,54654640,264210538,487453465,17998798,612014994,220717985,307306410,1000000000,35424781,438315210,5941754,38803687,41340140,31868217,59041,266216761,535661743,301910792,42066845,1000000000,193735819,53420741,337395813,73385941,23052726,350785774,795870520,946785983,415763054,454913923,361103965,604433242,222530728,38862498,4114898,47648529,263098367,777305259,659229622,265563849,276031313,198183702,60452021,46500979,90579611,425156286,967078322,377299052,161967055,629098799,4600347,21247644,814801160,648795866,271013276,74030215,6729955,254045298,8114528,57299143,420812101,16392436,1000000000,1000000000,198153081,244816012,274597911,1000000000,516232217,4027696,15664435,79595344,223692801,920878997,22116413,272487241,5933666,274043605,1000000000,18779605,85427697,1000000000,1000000000,373184421,777642304,541100704,30173162,33570924,25286918,67155876,128106668,343458231,439512375,27168647,136408259,653387820,113460543,62949171,815617559,114627625,229353341,188370959,551820534,34342603,311848553,5345249,381594297,17634046,75085423,37073619,204173292,1000000000,51545680,26443978,115718864,89855464,174848687,73259631,159789852,136270034,15177629,401798281,1000000000,40991213,17687801,1000000000,2775939,351796192,137031130,301640635,108220474,1000000000,1000000000,519705541,838449263,495238927,133560780,34423863,640622843,10944353,14489140,665470528,389287816,26512129,6021591,275125012,210817225,434839526,14506832,342889759,475145248,3181737,38512881,10317480,516913,6848990,43630013,203460963,7762327,105748282,63115665,25721244,52655804,4630835,74588999,50001798,39910338,2694444,87091270,163452444,343274113,379320103,272801813,598799345,88068191,31207383,562881920,4727823,499752959,252131045,44844419,330294852,226368739,1000000000,172554998,28287060,302582181,1000000000,39605943,587219343,548476244,371359847,1000000000,312253694,424658229,235940426,159550223,112291381,113680067,107668488,98228607,102135502,22962253,19820506,217147906,178712026,35745786,67805308,450481823,1000000000,6214601,391357019,279705717,112742866,1000000000,158461311,101613732,72309126,347328938,288978265,1000000000,125652361,24172103,499573859,10920865,36054273,736358695,148683217,78185242,925829053,101808512,463159643,242022690,192486011,220335398,108283864,44461296,138104108,489457782,12597071,94622665,481109900,57239282,492193358,304120990,50564536,443915004,207714027,118772048,681137391,122833072,121509141,81650843,182466339,146586279,358927577,251540546,77083968,121645395,1000000000,114509659,52396258,343439559,1000000000,74086426,1000000000,439151897,265648671,4831011,57806821,86299147,160854513,487176718,46594373,846994187,11668660,580771345,260168714,262167527,123457794,900818728,260574627,467544598,35323069,1000000000,1000000000,4855343,148067764,13348222,95123035,49706582,210861176,232215764,195791790,421180493,187882953,85060840,249491257,476942529,92636770,89938540,106789172,486195948,311395289,171655676,19947602,1000000000,31453466,701927937,26338222,1000000000,430104683,69413870,29335011,1000000000,1000000000,306843869,1000000000,206531457,1000000000,21753946,181941190,15033310,93249269,1000000000,19847187,16208330,19604864,191535379,241098068,402964145,162158218,561601091,19897591,24096978,385202659,159533589,49660009,515708298,75018575,127213799,1000000000,11016306,59672805,108749016,4457854,434088308,238607066,261490169,50190071,201332793,80147933,438056703,79751994,148420380,1000000000,3202644,10267442,39340213,51858920,1000000000,67198848,687474565,82954616,258331612,66738204,60977699,414981007,378472146,1000000000,31223200,423780761,1000000000,175037680,73482176,4744324,92430386,198843047,29689910,13957964,7500340,59873761,575945626,266517474,19389753,5484798,146740598,54712273,231851046,530092159,191284238,260565881,222270258,412545222,25159894,880976939,106444302,305729934,43264965,309683882,211011830,91839424,3246832,144287330,66044432,682827967,1000000000,90555380,444940097,1000000000,229268860,397734769,40356547,8228226,244582928,99644149,226958776,194688142,903326792,861713138,193847430,1097789,94793591,79635988,11149593,87892819,830703117,719585350,210787,74314110,138208984,21820355,782220636,314029719,65271234,77410257,584168584,124226125,46224112,10588596,117931836,500668332,328831868,1000000000,35389112,48979216,76558194,315043062,1000000000,17725687,61638242,159173499,227843447,371306625,83602484,80113714,1000000000,526201693,329456441,47383645,124269625,10722321,1000000000,87828955,31671882,70334402,150178125,393861444,378315555,6149135,560387462,168543575,207937509,40478688,35531586,57104240,1000000000,1000000000,10900689,1000000000,382662747,142157247,49354965,231321907,135645974,169400815,26244393,393778669,303380264,14271569,697027267,87551446,239169547,341077856,997355952,33973945,108288055,287098900,339335643,395530168,12473814,306784777,234862919,55875843,115472440,1000000000,272853015,11725862,389817298,232018342,36659474,3978227,18699856,65110324,148070354,64776170,1000000000,6039231,2527249,258845398,48707461,133710736,17410872,568817273,295014878,241067435,1000000000,328347728,261420081,179683578,122554321,162238873,156302973,131647894,150858200,366147023,539684324,259695683,47381170,75705698,209522949,759541033,35209395,777466076,153496097,885724934,143994644,56629025,41213100,426248785,229091329,52545894,1000000000,563044743,274610700,325695237,442320016,263380988,694530568,188866386,180039042,710006478,92284367,426751480,241372074,39533384,26363030,1000000000,1000000000,179658158,20845606,127344684,2611437,30357662,72105460,1000000000,2831590,59271399,96189264,1000000000,163554356,142954656,1000000000,153040756,774361458,1000000000,132619199,31062826,291081896,59447217,342230590,420908962,196653289,1000000000,1000000000,45117771,32767972,669713034,238303105,8760040,203908467,35997716,296451828,135612783,234085524,347814522,96226198,3451461,68272254,4126157,1000000000,131421143,233806339,683948613,1000000000,162098597,105137084,162096010,42620081,227101894,136758442,1000000000,0,1000000000,147281965,69566458,915532118,92624384,19807762,189813324,281124797,83355127,255972438,241491571,7979474,228320530,152803724,89050164,96946673,17141815,732727979,68276045,226328397,432144937,677888223,364174775,84567498,302312058,1000000000,184335873,150494997,845181582,831981329,272459883,288238005,21968071,1000000000,1000000000,1000000000,1000000000,250285723,9989607,395742118,709082366,34918177,328490770,1000000000,342532213,713557303,108978896,291961102,4932817,297413971,19166770,339316372,16149971,238705599,227120277,581799013,49995817,1000000000,344774139,213494312,143081417,120394987,182608024,63937536,1000000000,592302657,62207862,1000000000,49495041,94952610,236787013,310572584,114954931,544844037,669430529,3019996,1000000000,413657833,148786650,1000000000,47119223,331542537,91909051,209528363,116588043,312745273,1000000000,317168185,73337172,72586026,343599916,105079764,362910387,471065915,403708951,290180394,37489539,64015639,3068003,35508164,215300324,163570814,36344651,134335717,216629244,1000000000,1000000000,59373438,539464069,110813304,86387189,14601389,7643633,40185251,1000000000,18415988,192525640,166836778,255364355,1000000000,48292448,69552202,720231647,683363361,15466776,19048952,29526048,28928858,76512729,97945039,21908224,72171618,1000000000,225930452,964084856,54407589,492739171,106882172,28441220,523252263,1000000000,123796894,1000000000,47303322,138646747,207995475,65295476,614358708,42278403,1000000000,1000000000,182623780,118916266,239385510,5386529,80696709,188245758,121326836,407030011,339861322,322964474,409586154,171377419,1000000000,126848054,298434156,335280647,6132854,4878811,3031430,1000000000,16717665,11237786,278190730,82181820,127581389,1000000000,170876979,695636992,104848695,12459972,620758558,466864981,56785319,455104536,190919951,417956562,384695609,63482745,54483965,38821543,4710095,152442547,253064484,318613956,394354138,46059684,353414116,55008960,419238301,112950826,1000000000,210482561,134401004,588176138,1000000000,970668394,28842040,105679482,1000000000,165097785,98722948,231308719,1000000000,43672794,388752255,1000000000,300536725,181963798,169907353,248715757,336659747,52773964,95780639,35316871,93551851,117884200,109618525,311400973,534834632,23857178,49721650,58204288,160176847,99740542,119676706,719238524,183735637,214835011,532255,36866756,1000000000,439743037,313232499,35573125,263402531,6208313,9973944,83694778,29819669,197769167,849969665,347096526,526829401,1000000000,120910928,397070981,999758639,1000000000,220213712,58976729,292913081,241961251,69855854,40089697,46555653,1000000000,298472093,439940235,1000000000,139364700,101778306,117445279,2104716,38847045,270355185,240556155,128720239,4075748,128808841,185990749,83984353,6020709,4912510,49766,226703381,1000000000,112958873,221294409,1000000000,44402401,392921945,260378213,278932724,355256027,1000000000,13532475,42435187,508696432,221259336,76451319,657454139,26601304,197027431,248520881,711606329,84602778,1000000000,161376763,38428675,161050948,314409496,191684468,76337239,55944010,1000000000,113524589,346265268,51179289,6331457,298820892,250218864,237953660,70327116,29772380,296966513,164406886,367625444,211747273,342704122,1000000000,205880641,71937681,262191886,319498591,105413141,381780546,167757391,24341127,119326598,386466318,289648703,35951722,172495439,7593861,381958,16289041,23666863,26439423,164024944,666655115,364982397,63274270,133730371,1000000000,1000000000,1000000000,929532364,169719423,94704420,86178424,576502516,456663238,80156550,1000000000,13021958,714396197,896247845,196050552,32300306,166615556,233171650,10719088,267279458,2110093,165987858,151574058,1000000000,1000000000,218142259,77970478,113713838,18509042,377973833,1000000000,272209795,14111534,79269939,266199456,261347876,66082671,596056242,305793841,284303858,67098792,461392763,1000000000,24536136,45062271,1000000000,30916567,413203777,296914382,207762501,51519117,261163920,251176749,72216593,160867942,91604108,277631715,320255407,143949354,1000000000,398737101,89492675,200838508,227794334,10647712,280483203,1050179,110076092,98065786,64256202,482753369,178605135,1000000000,56068609,45047106,81671591,125637937,81045005,54363413,3222690,87871816,878087786,192060663,246629674,1000000000,1000000000,10208099,1925727,133478977,82802805,26320034,1000000000,219415159,370788439,64758266,20379679,299567636,80895528,143685012,635021368,270831016,366531434,564901883,0,253450776,375995836,1000000000,271827202,1000000000,1000000000,204478830,121908055,139818031,244855059,488156580,61028243,120624977,44847816,83897146,89110482,271036492,157791896,69451543,200830319,15847989,42255081,428627917,199401797,247019324,921823,324581452,62804876,7060715,196289136,353680378,124911591,1000000000,56448521,203313725,272569182,317494105,1000000000,65065075,41893622,143123410,22918334,72135282,64181088,160601168,91194039,187928720,412351481,212231248,218968399,193783329,154510264,454280131,47869514,191851222,1000000000,421791831,110526527,208099561,161078146,1631220,56524006,299964439,28511971,1000000000,96977405,65839874,215962266,403461488,251508122,57169999,53638397,427009392,517056421,369981432,901684329,90913042,49591716,86185451,362276638,17466440,243595452,467314704,328763282,21283778,69076545,175996463,109994245,54719689,290906488,1000000000,146688,41574298,1000000000,345881147,61142633,124350530,149954568,282796033,221667863,2219733,11497692,1000000000,3190213,318384437,1000000000,87792807,280518099,35216372,38377437,1921289,13523528,1000000000,9074817,73497307,1466393,186615177,109203982,437015095,70342302,36863565,341043384,33048166,6444096,6264441,45897815,150827947,194252210,90874043,74009,62446239,582639563,5494483,1000000000,672103295,440236800,260981499,619788249,45507435,752250588,163234509,97637817,94438770,88205680,164503577,38760207,61441313,181847269,113013959,129581640,20122517,85508128,1000000000,0,12183973,13516662,1000000000,250879917,1000000000,58826072,123436559,96669017,161349635,71654885,53002342,45117627,49326425,359486,49004164,367323883,228724251,372475060,345680486,94419945,213138959,167944474,329379165,611338597,821415326,64856560,169002373,145933263,281710916,166778416,257337239,4005925,159578124,765464661,165585336,245559737,83171694,746603794,404653755,6667845,4989593,85803886,240659406,61248426,167054792,70020455,83353783,340663018,13789284,369288775,163386234,113041119,24481554,51785941,845630660,1658530,108305276,2003449,271789354,227865481,1000000000,738860080,157341426,1000000000,116676804,169244538,202114799,297678848,13250260,10603156,349815111,179206564,1000000000,40780906,773040402,115867350,78033828,60882999,51839221,82559108,141576939,279847460,539985251,274446895,53500777,82498468,51730073,88724066,154597760,1000000000,284186300,232272886,44460540,69565150,1000000000,100801655,226497675,140322428,470103038,480513405,62986267,33993638,690205800,432827360,202876827,70073879,17562257,141414793,140393114,197729877,420571937,7985868,336230044,99261,615783133,296638296,1000000000,39681581,203891131,180740523,254129864,1000000000,398278782,15605832,424205267,41765773,282039700,46491606,1000000000,1000000000,22231554,353601382,191861083,212049145,885362989,222105738,316800539,111692187,639679338,52183100,146807605,712059733,426060339,12470075,332599415,854763619,16092081,18941464,1000000000,43479763,60127766,76108722,150376362,46518337,81316322,91847393,547696969,242621099,396250638,152736314,31611000,1000000000,17666230,129171320,2640101,808032000,269472952,172510234,259361870,532970211,273021946,93456846,24912731,63914298,85254681,9914454,73996540,56154315,247441076,1000000000,92929685,16267523,830652852,213334035,251745703,717847052,986346,165061598,692052233,59468350,184456347,177823389,76390401,589570499,35066342,15936560,1000000000,512904285,28411411,680713988,337336482,117463180,500782473,266340246,380162,287512,234926732,117018917,15983985,269830721,168393876,785889959,659155680,445007807,184198956,349694245,89293053,12834832,58374670,27537029,491611792,626913867,1907361,21608411,4877374,38375087,576009270,941044506,82281991,290031221,143346768,277949832,157234804,215742185,56340435,24578396,402297962,14252075,60659941,19827521,23945626,203594355,20461266,148055082,235285181,6284935,29034795,314060550,34790747,7067269,184915943,590485002,214670004,571843838,130297978,107595540,283397538,415434649,13260397,289883567,1000000000,5158137,93590012,169803724,130362053,8117660,1000000000,1000000000,102058112,90573036,262276344,321261694,109833306,10212065,273690206,1000000000,259154933,573946457,86085181,150408396,21807203,20176531,65994424,1000000000,405031130,128571088,1000000000,8463495,57016646,252883085,203533945,371543728,140202845,895087274,32348052,205819916,60386366,253181948,12579269,1000000000,332262217,1000000000,185140137,26726811,170525585,212101584,198254961,49040370,159742790,216731913,362605748,476623636,6146544,98060109,7137187,75659078,299967248,230301852,264589649,1000000000,79714526,24319184,23416246,12326004,24048959,1000000000,268057183,8862683,168017835,49631241,212895801,471572424,20083575,1000000000,4894422,269225619,210266438,936764292,148707510,211508924,15599469,175815099,22010626,922962585,6753976,652703659,305812075,90434408,191794231,1000000000,243137602,96823992,1000000000,304829664,156288537,194615174,483478217,689485956,342050406,19791227,410160410,35980465,156616815,76699791,22124046,148531045,7565882,380508867,74821492,47383171,112961278,38557400,154081984,1000000000,6065497,35945747,74333867,164546568,65290400,1000000000,358602082,65237295,477481502,8138601,1000000000,39457336,121972328,168993025,47475194,4605743,615743995,27934627,224074239,246875631,19865095,1000000000,677613362,136969433,90709782,45586576,44571895,140738383,135170333,1000000000,904336636,277258088,653814277,325771,1000000000,358216998,480003331,16671210,309183788,127604296,1000000000,2151823,31667038,200841975,585447717,109671522,33431389,557627975,19306653,137294558,30239314,69159306,77337116,210726678,1000000000,1000000000,36760352,77802779,139076810,3707635,800500646,65387652,197086257,3045050,2387448,117155438,3514308,689440715,57270659,345640158,1964755,143500509,722349316,370511943,546275388,289468617,52053161,270736726,277501795,206424901,1000000000,137263528,911321395,65817864,173339345,524910210,21746234,1000000000,255848202,407518799,220013284,203103682,1000000000,11058249,18368233,334988149,56819168,71655883,481179074,155768514,34561341,79785658,31147537,1000000000,55440219,20757852,568207736,49602231,231751568,532543612,250822811,48297753,25391890,151377072,1000000000,331064827,1000000000,708327653,432204536,658678541,102446702,675375000,462753483,143640041,26928853,270924156,100610909,104710982,61443749,1000000000,1000000000,224730339,736965764,995184366,334830558,418097348,1000000000,187859665,74782484,72602132,1000000000,181178334,921936736,1000000000,406760935,155303129,281532641,1000000000,137950667,42860793,8375249,111481504,351849706,37520493,170855597,12600663,330508448,1000000000,103179519,204391785,1000000000,768536227,127876636,2740851,46307099,609265885,615069311,851867260,28922358,69900636,4014817,1741485,27972193,119791530,4867405,201526932,45580006,67982197,114115718,17496185,512599522,266213950,327334489,134429444,42552185,835336945,433916804,32647980,169146567,820432227,89998488,152092245,221384625,41763130,66290597,280385462,29009156,140293507,57796718,360683945,1000000000,173231004,53176166,656974301,89000394,253535622,73077124,149723650,94292815,34727502,123416442,9646383,1000000000,586590597,34732831,476864470,149996902,34924874,161009669,133851496,62659199,162304654,170608146,54646736,75238812,256376801,763999650,166409268,19374854,43002498,25501078,126927795,355390360,2500215,35908739,47734055,191325724,22671531,1000000000,298817334,551550275,4025363,1000000000,238391721,1630818,16058764,1000000000,557095337,727752372,200941868,5825188,116475103,326121435,1000000000,5958455,1000000000,30528408,208392491,312304137,580605500,1000000000,937991207,345715251,105660458,138576034,74373009,1000000000,28000442,26335227,93069676,119804521,105804262,268229373,167389276,128099115,51348622,113282329,103899020,4673193,98306735,490711441,63473585,6412771,50543655,117953844,14624330,261952618,83334966,164858288,0,9540610,110502669,335650605,36656420,152182275,1000000000,120517422,261393531,848842542,105571316,692894536,39659328,103678433,328568047,267776219,173182629,290380951,18760794,69765701,55704326,285204937,489124216,105322584,114001153,71224030,117205925,241184143,286301596,181799105,175854247,285188197,140400313,297085345,191625618,191614965,130668548,274656087,354442616,848791752,20131244,1000000000,48851610,380891285,236878611,37293860,242752169,943946,248610936,955672154,33980784,11047687,321772760,128804316,36597933,93944670,1000000000,256871851,490681743,656733260,459628803,92794792,40188051,367965727,690335687,683763286,197573283,513231913,114428596,278668126,46369828,598746348,34286810,107295661,269562008,961661324,34054761,492117492,146345511,58636397,757748893,355148193,151209351,40579003,600505570,671089326,138137907,173362473,911960757,117517300,376475,627213029,7364089,228494472,1000000000,28058363,41362595,528976154,704060690,31142605,3859902,222121500,279912477,184033954,95704540,210926,132570036,502500785,102382876,1000000000,1000000000,141307398,274431563,159382727,1000000000,63363519,284076401,295973359,49244546,980559539,1000000000,31792835,14242382,217225517,1000000000,1000000000,50538909,1000000000,339307338,59703956,50539254,17450459,124366957,1000000000,366662625,562633145,573287519,259225994,62755780,76525047,386430648,15149189,7461180,27034247,11545594,24277589,202456705,5463639,241225133,631179726,8861402,93210129,16647281,12748154,170879911,440531923,108131388,37439978,81568220,2653662,33931755,960794983,89813660,476785629,2589686,196109880,2882256,117074830,1000000000,652267232,957397381,71596315,4395118,332045077,1000000000,2402365,110831605,1000000000,79799333,47092468,188299893,44161,46838704,308316619,225552101,9995171,104714034,146803461,17391042,105776711,46599964,422673633,11548196,120073611,41922061,2259891,36454554,23409249,100246055,191777048,342338905,38553790,37556695,1000000000,691060578,29226396,73644363,246780622,24140344,129860037,218624526,97712837,51364039,436271638,558008626,10780928,1000000000,33037413,491154364,73390940,265178770,3210954,141382960,70194141,34145331,315001964,146906088,236377951,283518883,526947258,137792075,3025365,178357338,116831666,24319825,68711566,1000000000,45705300,48190240,397912913,207786068,406219985,1000000000,105474472,57940575,22307910,326069942,327929337,268482900,469101021,412567052,132248228,1000000000,438579793,83096405,1000000000,340863335,14274349,163966897,1000000000,28982449,33835363,1000000000,25263177,50262203,3211024,58826912,243360311,1000000000,6867098,570094022,246027998,114691022,306134248,240455731,485134540,1000000000,304268271,359922226,850502899,104907467,941591273,391709599,724479047,5141062,375897171,113799361,229210293,299326541,720887893,756464813,1000000000,191399451,2174443,607923226,57936867,287058828,295781208,1000000000,30150971,101674893,363016605,1000000000,1000000000,212666805,433814293,94004990,405931661,236275965,597704553,133277088,1000000000,20215121,1000000000,425085143,327014446,539430560,288767060,35384466,295497015,30451115,787149518,998163647,492373537,272282400,469854974,218051016,55492997,35022287,168639245,36384317,586691410,668842667,281075969,52606174,342731379,1000000000,579960243,46549832,260601308,79559538,309581393,183853032,945932,95507800,211488886,78325319,158951581,91097305,37789145,1000000000,1000000000,502989418,375600636,112080349,482447312,21390104,18739115,139817951,991018206,84727315,39502446,850596301,49077323,371285631,87069547,105943503,352202506,1000000000,15168654,151356139,323697334,21079636,193899091,216968875,178501284,367711294,58211917,490006885,23970534,73378953,119210731,1000000000,110717886,1000000000,488687989,6322819,170319944,24748571,63846830,12382226,660540237,1969287,97078702,146138115,71824220,62469004,224148750,1000000000,340321565,84915469,19243631,233588799,53132432,4513411,78827178,36770213,48773896,27180265,462990803,175611763,359162816,175221025,341590915,875827987,489322833,25391625,76086070,65041241,40256053,265500595,27763443,8774812,132924327,163940737,874047375,175653717,1000000000,1000000000,121086708,700771040,50819728,82607136,148466800,259948242,1000000000,331128886,82462709,120758545,1000000000,4909241,15409640,50695388,50001701,103638244,109844518,1000000000,717997175,344214594,956530326,97273022,515260389,276625641,396108344,1000000000,179364348,88257270,32082390,202775887,162901193,39343786,162716638,4476622,1000000000,74253714,124053612,1000000000,37617306,1000000000,308155417,39105947,683938207,284258504,1000000000,31008316,180481988,1000000000,117793629,26820534,31153373,445084202,1000000000,112808539,1000000000,26479569,130963993,1000000000,60874018,3336805,1000000000,248649476,24570959,84078085,37496836,888056129,972343649,659531044,67644744,54678621,69522422,252221112,137674222,21575690,2290888,1000000000,89200740,78506267,81583769,179338301,49150250,104871962,29224650,190402442,178862128,1000000000,344832953,537517122,100767995,37173468,262383500,177737886,644211661,37019889,192573682,75248730,27853557,2389495,185430085,958400454,125592962,1000000000,120002144,147672305,110903901,177618338,190510320,6090546,12092004,240649097,15868429,258973820,59646005,144449844,42336699,106294483,489963026,21262538,73761877,31210338,21335367,396090852,209429549,70799113,1000000000,1967189,6045703,499716292,22568617,45261275,931971566,363410829,342636279,166268366,699585241,551159505,17932634,757098571,2158041,166223400,126708163,886051932,79220335,91491612,192591337,1000000000,120250186,82654434,699333727,57424780,613179544,394564406,19025512,67248743,314222980,93835197,43099987,175874972,10544208,95517526,39864529,784472097,1000000000,20597293,131331300,294011508,1000000000,398442488,328810460,168090872,173713342,99015194,5041112,286839812,131876598,381738263,68239851,456821741,18807498,13688163,47760358,292673648,13183738,288280120,204257226,499943576,301342217,241488585,326885623,18142915,533998445,79730329,366528649,15309053,21950200,263579627,234345003,24769774,349049960,168370823,123594039,156811367,111863866,26379821,33054009,117572495,138915159,57207722,13709385,220146365,177229024,110704232,399174967,226491814,114410160,309338918,231441831,1000000000,81685685,45159033,73424358,189579330,243948568,270125778,646383806,46405243,284138329,249259647,117915994,3646784,1000000000,342371619,183476109,154193853,926697,194426244,56076070,1000000000,102891484,603219386,104493520,355804183,20932563,57016483,27766854,1000000000,64128179,126771257,45535506,72557737,237876712,33753155,7068645,479618984,1000000000,7162510,473326747,278721813,3991826,50257488,260749892,768481439,1000000000,164155259,393932843,11970184,189854611,132780350,50796129,17133230,56284719,101958928,199116641,3252315,158619245,5341536,4286735,7774068,200854947,120306568,44664301,248681137,62922779,1000000000,121161394,131181834,60814503,42437958,224737673,363195347,14564581,180470266,822399565,772485075,1000000000,652071676,317646127,149486442,481247453,148414066,55363258,12150425,1000000000,293231308,125440771,264170080,7720955,28206484,302116240,1000000000,23567659,44808692,8749811,127156438,42071170,180351780,349774463,84666101,488233284,130248149,303710159,85204750,316827592,79619889,1000000000,21802933,13764467,92773949,296627705,101591836,28270101,222151310,823867346,108961784,936189203,545439684,321127262,323880861,299749951,130342106,186302076,176578391,109078099,446618443,82963475,643499122,1000000000,136665474,362679584,185119431,148755635,707805781,1000000000,160460134,665101793,73082891,222061738,520879429,371565326,81185581,17081610,117681216,129058716,587292085,140235196,318323514,422526013,105640127,43280153,407868898,900116500,23896624,94252526,1968201,219396518,1000000000,605000,73957269,1000000000,28721115,20646470,112561772,101963407,22411250,192840134,2727316,41719571,1000000000,39276461,243896032,121689355,434592721,1000000000,144237141,26658566,10360207,102795150,254556325,61384694,3215509,92222847,186518052,30128818,1000000000,174347731,1000000000,36197445,81491549,55799312,219374928,316981690,1000000000,19633649,1000000000,39442934,59169478,907751627,363041527,221493226,70361825,74757836,286809387,684239068,102372393,708854907,9854191,75781997,461000194,529904076,3406321,353924898,256998386,91391282,13998209,6272491,271898223,208407,90134082,34779303,1000000000,12686944,182566588,9349200,69672339,307083804,58590870,3365221,72253385,199638209,103521301,284628944,641781445,343708222,640740,404785575,214335762,563194966,26410999,208401609,135037496,307483659,146669657,1000000000,462272183,72002203,125840470,99847206,24800730,628525551,1000000000,49538203,103763633,264022395,776399835,1000000000,16379422,127121093,177513365,227314699,33903039,751805202,385456592,65313667,539601499,165006152,10918747,184127746,240688383,313280408,521724292,87182255,94921990,45707619,9298960,227067985,3563988,202712873,95093550,219661634,1000000000,72872992,142581774,250444159,21901789,450163852,1000000000,34937176,18615952,152769259,91134016,160716395,242757537,351412026,103224960,1000000000,73729114,1000000000,57251878,74466270,4198100,1000000000,1000000000,108188539,114253881,20430159,1000000000,39174899,134402774,197873522,531715570,10349026,30164055,24726792,272544529,33969340,23755534,148139218,309521,46172190,87116209,17683841,224117283,92494551,40901111,359398735,192646181,278566673,342695142,205612078,113295874,828156327,65891649,215411221,108623339,240652643,450426520,237636409,95345476,914643295,177473740,68107287,330576532,415584795,727079155,110693349,170581031,219717224,1000000000,392811914,1000000000,91695982,1000000000,43615609,63586780,61843552,403108232,255626678,142609233,225342556,197517017,539332385,71860014,182035970,224495801,104753086,52177271,266972,80644679,65971106,107744103,10944833,1000000000,219611167,36858458,395500621,1000000000,262456437,1000000000,55601298,348699716,142056173,433295409,628615722,348755905,368858521,15817696,100777776,153542262,9296735,838316634,755247083,126348557,84963684,169455374,282222581,377207315,196825508,84078093,3842000,46289838,3358017,52873215,35788284,142859812,6715313,176109491,100929093,1000000000,1000000000,5736996,600982711,1000000000,178275262,1000000000,389660799,140753837,322427243,254326055,109080675,1000000000,43412277,73911885,244658296,1000000000,127557704,130870161,281514084,1000000000,32708437,186300658,72832484,226886373,310607907,265520555,1000000000,286261338,22807733,137459214,234553702,29980358,383636838,1000000000,120185052,160101002,231087130,82293163,19863411,30417933,1000000000,835504751,231801793,135222332,1000000000,729657694,24891733,23753199,1000000000,173815503,249634179,134383400,235581084,1000000000,90512629,1000000000,225353827,31953640,340944774,143998852,23835202,327648811,32068643,49376618,1000000000,4386055,89519043,210280744,54115302,231379803,255731631,255087182,269231279,87720917,133743648,439469769,330244993,227733657,146964210,515469142,737404082,526710852,35722240,414162250,167202581,94455546,12118298,1000000000,1000000000,153493738,858550,383727798,987300743,1000000000,167979449,50407349,30945759,134106205,163339036,126640592,671211929,149707252,321415082,41277850,42800628,108189927,6358985,153968047,1000000000,494071315,121801031,371415297,176638822,285720603,183693379,16144732,110517484,787271988,182623154,4257702,23025131,173195719,5700582,351327111,223467177,865780898,129585115,258488852,51346184,47915576,50952714,381493380,445983712,593047663,127866240,184345005,143761001,44047178,922862062,1000000000,285458712,94998323,18362222,96978460,924578250,235425982,156982678,1000000000,1289587,15039027,72673520,42015748,47168583,31779147,1000000000,25323536,470663437,10053664,1000000000,175143493,1000000000,101801847,165216222,147723329,1000000000,1000000000,488562964,259767632,149363889,630198368,121927093,191387062,106233738,78274784,949983882,209862993,36416489,165959196,127738134,199322118,693708614,1100144,146693124,231189887,1000000000,235453841,245019,211102488,169620905,204379024,105009695,103531936,211570811,29209988,168554615,346837475,501447897,281530770,21325448,96843906,23174376,349048554,99992244,77235596,167933369,56661187,266608407,157490456,88306718,22748295,8372129,4344895,324797057,94715152,23125700,338822821,14739895,37750792,70011145,424190,1000000000,106846989,53409507,809426623,16818197,295014484,86903820,893685029,124652556,5473105,1000000000,348080606,173934137,132946775,199864725,120493378,373870964,106134659,42852865,1000000000,1000000000,4276580,307724288,92007084,325263122,164524089,337557851,58630029,15331948,54505148,34271182,271225207,1000000000,106064935,728158084,104250104,109033940,147882977,1000000000,226836172,126998354,330159789,463554403,126538983,1000000000,76740868,31167971,1000000000,71533065,6546872,211871378,1000000000,12114391,1000000000,1468417,111798380,283445543,109220396,480145835,31300803,1389558,16581193,203270907,1000000000,969506798,34060483,407794338,98360244,143770370,114952440,619272491,141845869,4859545,1000000000,1512661,601829811,1001125,324470783,152268406,68163480,14243300,175412053,141881815,569829693,161599001,292434461,15993023,157795262,151230768,252914685,587992174,37009985,26251650,209798422,64178482,313678576,218388842,247571425,40313047,298027039,183255803,401454695,12321474,163502938,1000000000,475372289,7758344,1000000000,211527865,1000000000,1000000000,585414750,70640603,1000000000,1000000000,13173757,693990314,12943145,30825760,134388977,159719660,895508527,727407584,578705030,577267813,87913265,110987771,810358167,113322402,24740833,120875639,133365822,2252820,89113438,121418793,532009627,107951935,360725995,199422705,319379904,73246970,2730321,140896751,317389351,423930035,5760027,317442616,17658144,7959285,11270798,563148908,1000000000,879231999,48770873,1000000000,257304923,943580601,193982060,294828618,120397044,276404066,237934528,366514717,84497902,17231806,560434068,336994342,64797270,382543167,206276175,339413618,44559357,199405235,291640473,205327944,221325472,609159780,287414344,829535897,32256571,333833188,106224923,306747,661326326,30198921,401678685,360643421,50138611,4012979,21834094,14203777,91796092,52039370,240931791,187711032,87710963,43062161,1000000000,32646490,12303959,285273865,239304139,242628629,393130339,52234763,164775376,100910970,47674560,375530,201939035,49384483,99125154,34166417,260147051,208249297,1000000000,1000000000,340529483,11293725,112549437,1000000000,99522284,410862968,295098903,72033623,901063673,18180117,718765566,704637031,164773271,138356315,77906079,249512956,178369439,57041992,237913585,1000000000,46281376,116561020,138387580,546853460,134344713,874294628,247056544,821224226,36996071,1000000000,142027468,1000000000,6168043,12200879,2081692,122891785,49239013,505788192,363543011,19677520,1000000000,4128211,76427266,1000000000,326336625,393434719,137621555,1000000000,168287380,326704615,113885085,110912206,396790308,1000000000,1000000000,319216407,437869240,116549155,685613233,1000000000,159155264,388439877,597061549,314579688,24637191,165556511,582100797,263736502,162844597,91469445,127054244,37957150,9443248,77103261,120718342,47534518,1000000000,82700862,171534560,30275013,747443655,5701,519146822,35063299,19023110,303714441,569063997,206999640,29823609,39821314,19222662,49747448,271002002,178360371,202459279,229246360,103650067,283966926,147700067,1000000000,1000000000,398963402,65298982,44921096,524628144,268060959,1000000000,113967564,140586667,103006089,504523600,679019132,309371895,172795069,20319390,198806874,1000000000,220633944,56404968,252122025,383566399,189894291,14960250,1518537,1000000000,154566166,240951410,6916298,132425114,217709711,342897834,72114728,16932922,365990885,128424129,1000000000,554656860,4717716,204254080,28784353,725586512,4581466,3198148,349715206,191857737,159610715,1000000000,214103948,199224683,352053694,3824029,912364480,56191103,54593002,175329885,54742572,2102504,257410174,788355671,1000000000,255624970,987608465,1735,261146549,1000000000,23827123,27434764,77812250,1000000000,254029463,739856086,136083233,147831970,328438515,212286022,5131183,367706034,259916438,270111789,1000000000,114541781,20739107,50879606,755310997,270423637,0,1000000000,34948231,100053976,82192609,8875941,10514209,629002026,59242069,570502047,77151285,297460782,47937649,113944215,109760050,71779118,260878637,402698228,216945956,132329614,168079237,188479710,43039693,52615510,1000000000,775266686,102779663,560774108,380979233,69225592,904624,81246995,513763959,117484393,64905905,83036359,98881158,1000000000,90174023,23188253,255599236,223429364,856272003,135595107,171951685,877975532,130663664,6733994,17821553,405682352,687033893,176878167,15629597,131301561,262901874,103982009,945248221,326149713,1000000000,1000000000,852689939,843300829,330222497,15498136,102732439,130733440,358731754,88933572,13200362,183283983,187205783,366390257,101279060,22994790,75697173,66030423,19151860,273844815,190891148,109678444,242144145,77636730,145824157,10463556,1000000000,1000000000,594143092,6113285,281623618,49055606,190117237,68915559,109554748,226590276,124199191,401404240,799383653,596988511,68877102,44827749,1000000000,1000000000,198733321,45200393,38939752,30975977,209725678,20379946,1000000000,161616047,372946466,105711908,532085048,244434575,458941,3929536,1000000000,41531302,17916473,1000000000,335016853,871867488,20282228,322579506,171909781,657397488,1000000000,194809953,18617854,255265995,875572544,60998064,59216664,137110380,79000582,16798347,50484151,12506000,207955805,475556438,1000000000,52695151,25334668,10528438,231491562,37628000,222225285,327333330,1000000000,131419838,217584531,254861688,152553902,199392663,169107070,229059325,114291257,453678489,27210564,55728675,368333946,114573443,147160944,14248907,98429427,41707867,274270170,1000000000,183363073,34893000,58576565,8037272,263232729,125013971,15213421,139200908,1000000000,13439224,271343930,178191734,82364947,179923598,80492408,297563651,1000000000,349843749,259529711,287354149,124670314,282124938,401859513,5556711,67792245,1661975,1000000000,412631451,1000000000,13170085,17224424,217287188,657725749,267956485,9868208,707326451,18521680,515028816,156422325,200759598,1000000000,153607686,2230955,326405795,67681504,21095556,29543380,830914439,391194292,98638911,338493589,236342492,407950553,297479821,580045316,604992295,73387036,70732290,6068913,13650308,1000000000,123765111,23030148,410146427,202102509,26561626,15825737,1000000000,33146786,136605329,1000000000,607368855,160919225,122839685,87329130,132215099,195630,345153915,562332548,681203405,18164631,32069520,118833493,178660780,1000000000,250790602,97247725,52585358,633189857,504177468,308579556,390978292,127407588,77793673,21391031,1000000000,1000000000,150039702,672294378,316074826,295462973,81721322,55087359,59400047,284690962,299106545,233453894,52425787,130179169,14278575,132417569,16559356,96526991,286880817,3529030,111501020,206331801,538556444,49828484,137669172,1000000000,1000000000,155059134,139493182,5717010,79860342,1000000000,188412500,258326015,10121738,55840750,9339604,19541779,583134311,272726427,116441550,88344438,2643016,139996906,163495282,75781736,555927631,510013001,454158383,20573216,10596063,597174692,68175861,34371475,646621730,142025469,380815829,300033672,616200050,481605892,63807588,206721691,1000000000,33961044,273330812,37016906,312069121,6384781,227616622,33237395,210281485,320039911,921619090,12947883,498588374,134296831,6689379,334797591,22627083,277486491,91030977,551900058,101226153,68753075,191651545,34968623,214117653,833871590,228065446,149430089,53330503,1000000000,1000000000,85127104,368806628,699750646,31299126,374805660,73973247,101013810,300561896,14810867,1000000000,125050885,81292992,9378294,143360154,415939344,1000000000,181069872,1000000000,436046265,275228662,74924735,369976397,104623832,318499990,472144627,1000000000,246725598,5190808,313942382,171702306,38549970,63714037,125780363,59770562,103646493,85777577,46337877,93359291,234297706,11167403,125723573,570628133,309092764,69272517,390617346,64107246,165012174,102853005,386224325,290355250,37765712,342168317,192217368,667681527,135024879,1000000000,29014674,397388460,153347103,424910789,214437454,884887578,41011871,23693626,320792961,12762676,1000000000,392761968,287507878,686786139,763716439,703821142,387547901,89712449,45097737,1000000000,113587575,86399655,69259092,274652171,311100490,525853925,110004118,118934045,157783690,43812603,116203773,445151082,148281447,181105915,486909673,150875558,137593018,95495121,3980118,1000000000,17931835,754149023,63145499,1000000000,46142105,143173441,367973519,66846654,188955351,79028722,131956533,324721588,97765200,1000000000,216977157,375274626,148051702,11935554,657389178,913441336,319041430,126134279,136397484,109275432,243540582,19787761,167365022,49761905,25201003,24968547,9900645,1000000000,76539814,4583288,42290706,190891264,98246851,430848041,10649034,55044731,470766896,454613431,615224059,106483801,105479746,49935305,85627796,184358405,115960197,61253754,110226185,52142372,318002380,240366212,185069771,358895282,23634603,208033244,341031225,361588515,43078906,136855763,68973616,130622233,144235787,92538895,175411461,102290089,1000000000,732257685,354527621,405720255,10369241,894963819,77987604,264064791,5619064,613496,88179622,40094990,163000344,1000000000,169686473,472231344,11662870,254782277,388528378,1000000000,49448558,123180382,24981773,269315208,54454152,229802315,288233781,20811935,331282211,6737597,61961666,25205210,864925421,209425741,412089972,104269340,322882788,293165194,21857936,578038582,342684896,423309707,179017948,484534628,402330477,32310647,1000000000,159651644,378540489,46616772,57786297,33849987,292570909,273723276,169631344,186573050,285582971,196382737,849890407,123448349,1000000000,300334026,14815013,1000000000,177342178,69724026,1000000000,281299588,133311257,117143511,676174175,167321324,322625853,35127926,2053668,172223321,151274977,28401882,250673133,62601756,388162951,30282322,364104011,60672768,167802354,198616824,86615874,67784390,1000000000,479273387,6663086,1000000000,414061607,688876513,371401557,897748734,191146882,630576595,1000000000,242587117,102913964,32970568,32374441,4497816,325777138,47219998,90752597,419412335,3138569,203542396,156025001,48386259,174883616,53085643,7064856,404855907,17347215,63084031,19910355,177499379,600838385,36524549,542160563,31013302,13606640,86341190,19781679,25825551,93760852,5841876,332320918,12018638,95940866,1000000000,52622634,530752,273021648,20947278,136948130,80167508,109090535,1000000000,695195852,317096895,85132837,8599042,22681910,909978415,291281264,13873366,262099233,546321748,396709717,470769449,269054367,833014659,3531532,1000000000,84551092,129101819,1000000000,265201114,229424929,109146479,207294265,119441453,481337897,84430463,675113116,704759350,47096383,31193136,52860315,125572194,457440697,721505356,166257664,4594891,211274912,73770593,15554196,155299542,313379660,226630199,365288470,1000000000,1000000000,283868422,97864629,17080908,84156687,73328693,55230676,75073955,10625295,327990950,123946357,1000000000,246059969,60989512,1000000000,29001933,626165468,115592507,64612620,1000000000,396187550,21184537,155308482,329956496,663188677,1000000000,310051163,1000000000,266740763,1000000000,234854243,249314796,617453439,34406822,8735956,767848812,214262320,290558896,36895249,276713743,160334203,2099346,785724138,396367428,283291299,425557208,40513063,46961295,106673136,59851810,99364720,84551578,59449294,8720559,338148928,75220533,138169933,333901090,79628524,39067638,51053731,94625666,96442960,1000000000,379005124,512211516,333921031,402763580,1000000000,97086146,122183206,51422378,455727580,245692174,209580355,1000000000,312472991,698196894,6615187,209022473,578117652,156051619,219377768,465026733,57467333,67305531,110451210,175594915,65611853,11860463,241600903,237651794,68654055,4859338,50521523,113466861,233348442,154619462,49452768,258023370,1000000000,247797386,298246262,339500766,438950715,112050413,132063927,286382451,340349729,189702270,128793,257610461,151100560,255691426,688845782,268336241,258458459,22519465,132496065,1000000000,270926644,620135802,842173513,223635424,421243401,59551151,172800013,123772116,184283681,1000000000,405905403,32881156,198973836,75655725,301135192,273184273,970235277,83240485,63475678,415429117,175800160,91178093,291536838,638623448,212673784,77193839,79168823,94692077,1000000000,101349634,521621165,1000000000,367060845,57422380,13336554,94863827,23171173,113168552,41476102,60072016,51437753,122946415,128795070,27378413,1000000000,755933141,571528665,99746955,540118999,205815597,136604721,194161274,1000000000,100732769,113191584,54760780,55216439,4684288,67774198,557460943,105606485,140420247,424236528,219942960,226400244,37526052,165365348,546764860,83243,201708708,231562279,773388772,82765507,199502390,233097641,201100001,38414152,881403328,704630,2563101,209513648,195291072,250494025,54437880,220603060,352792758,128870867,436949673,339914696,92272260,45247780,214427366,37764579,70230827,606334419,702645211,41096068,638951978,85156930,230434091,1000000000,103243038,212432678,355445878,533749054,20404016,61497558,118298933,252513605,104917831,61707694,1000000000,359664330,74958290,52397571,72533117,1000000000,29760685,343957746,42383721,1000000000,1000000000,32515951,253415125,20826904,1000000000,216238383,60226671,15268099,1000000000,304098373,188761304,5290307,79867858,113185958,30907576,280351147,350630530,125820357,129526649,2907315,51324070,1000000000,1000000000,355077321,196407326,18306458,89074919,45679868,15380212,480591571,15488591,93859858,1000000000,1000000000,1000000000,841987615,20029585,36544736,804363622,42824753,73545980,567049636,30361202,28158907,184746797,286091255,611386640,223809754,43583423,237422425,24415783,55049184,259413876,157833560,438059781,66942656,312630291,58166215,492735254,164597745,305680431,337934991,140291947,232339634,286344017,288865118,334443172,736334934,27388251,244664407,36385319,20688365,16464926,116410127,321323476,205567343,129037278,2378646,49457577,157979487,31701782,456153372,35834657,11819426,371344423,322327125,33107644,623748354,457589739,88640853,1100370,32396395,245319547,546054669,57719938,347765028,325049054,42722332,192790973,214790584,207863289,4118656,543520279,86843222,62613274,163973401,11402394,274677163,331885334,128529215,134933217,592910032,208794626,622269908,27961633,1000000000,249278784,70220022,63151842,862241127,34245003,458948345,37452364,145363447,42347014,149187475,225393139,82143752,269011548,32717199,517404030,2047866,52049669,182342481,136744878,88287352,260478399,432555140,420090600,365837423,64413961,41519314,1000000000,161925839,1000000000,828820432,316710970,7349054,252297151,1458445,179317020,237815010,234524363,71993307,144369575,36346287,1000000000,307541089,173681057,322571804,354054341,633078632,276167409,289887055,271467627,547917029,1000000000,123131532,22528652,1000000000,363761313,73907386,85496049,214574358,791187463,109217884,100520262,20623097,50146740,230337107,185682,1000000000,149621465,129672555,10430070,471183357,25179062,10890270,365564931,506082080,164741816,9931034,246154644,123310557,150074734,83440367,156226101,559689132,194403,424707340,23925696,296886556,28855040,154883256,1000000000,21843470,34709510,623490112,168904963,242352512,1000000000,69228156,334767616,218733819,121500309,5922713,272221892,1000000000,132565109,759791282,103845005,104251572,126799227,69619253,13528947,377782701,1000000000,202229608,77992600,474130317,136581608,3098519,137470605,137008463,175584351,312144270,63941989,488341026,98622467,134717921,324254506,248017217,1000000000,849548285,587269330,13573666,1000000000,362612553,16030925,702226035,9842043,16772798,138677685,187952148,121609921,19955353,170847286,72675575,5978433,78691967,224100902,1000000000,175037668,554480059,78842767,630310640,1000000000,93581722,126440563,638761733,95611617,713489930,6573280,49943146,31578416,156260296,308303774,257842366,295880245,35081937,1000000000,321670509,152545760,108446212,1000000000,572063952,1000000000,246731201,1000000000,165606423,81583340,142078396,1000000000,98121352,264670842,545918218,1333918,565649636,18833859,16376420,17104102,62875470,240768421,49656545,168212407,1000000000,1000000000,433816170,110386562,230924650,894570613,1000000000,202924808,195155598,182715476,1000000000,100889319,409594872,247711121,25492788,146064047,23030343,2012774,266796950,221114801,41231389,1000000000,203448433,108535854,1000000000,11302385,971609087,41947724,84370800,3662764,90325285,1000000000,438294611,28499058,35432194,69422416,169611160,6853950,1000000000,946995660,27014300,492658920,1000000000,125140328,1000000000,33381972,242323125,706603521,103334043,347923295,91693200,28286584,648982604,91751909,86720028,13099255,144180338,14429231,223931752,1000000000,181559494,244835311,135016061,20132677,102611811,306659541,118378040,13048757,388880763,1000000000,1461050,867799163,329421362,26993760,72929001,140214236,188164407,14608646,333239841,101235300,298273116,315170418,409908839,17040084,405472551,198261461,429574902,243129666,162692842,730574750];